Non-deterministic communication complexity with few witnesses

Mauricio Karchmer, Mike Saks, Ilan Newman, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Seventh Annual Structure in Complexity Theory Conference
PublisherPubl by ERROR: no PUB record found for PX none CN nonpie IG 75516
Pages275-281
Number of pages7
ISBN (Print)081862955X
StatePublished - 1992
Externally publishedYes
EventProceedings of the Seventh Annual Structure in Complexity Theory Conference - Boston, MA, USA
Duration: Jun 22 1992Jun 25 1992

Publication series

NameProceedings of the Seventh Annual Structure in Complexity Theory Conference

Other

OtherProceedings of the Seventh Annual Structure in Complexity Theory Conference
CityBoston, MA, USA
Period6/22/926/25/92

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Non-deterministic communication complexity with few witnesses'. Together they form a unique fingerprint.

Cite this