TY - GEN

T1 - Non-deterministic communication complexity with few witnesses

AU - Karchmer, Mauricio

AU - Saks, Mike

AU - Newman, Ilan

AU - Wigderson, Avi

N1 - Funding Information:
In the two-party communication complexity model, two parties compute a function that depends on both of their (initially private) inputs. Roughly speaking, the deterministic communication complexity of a function f(x, y) is the minimum * Supported by NSF Grant CCR90-10533. t This work was done while the author was at the Royal Instituut of Technology, Stockholm. Supported in part by NSF Grant CCR89-11388, and AFOSR Grants 89-0512B and 90-0008.

PY - 1992

Y1 - 1992

N2 - Nondeterministic communication protocols in which no input has too many witnesses are studied. Two different lower bounds are presented for nk(f), defined as the minimum complexity of a nondeterministic protocol for the function f in which each input has at most k witnesses. One result shows that nk(f) is bounded below by Ω(√c(f)/k) where c(f) is the deterministic complexity. A second result bounds nk(f) by log(rk(Mf))/k-1, where rk(Mf) is the rank of the representing matrix of f. It follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P.

AB - Nondeterministic communication protocols in which no input has too many witnesses are studied. Two different lower bounds are presented for nk(f), defined as the minimum complexity of a nondeterministic protocol for the function f in which each input has at most k witnesses. One result shows that nk(f) is bounded below by Ω(√c(f)/k) where c(f) is the deterministic complexity. A second result bounds nk(f) by log(rk(Mf))/k-1, where rk(Mf) is the rank of the representing matrix of f. It follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P.

UR - http://www.scopus.com/inward/record.url?scp=0027099111&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027099111&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027099111

SN - 081862955X

T3 - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

SP - 275

EP - 281

BT - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

PB - Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516

T2 - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

Y2 - 22 June 1992 through 25 June 1992

ER -