Non-deterministic communication complexity with few witnesses

Mauricio Karchmer, Ilan Newman, Mike Saks, Avi Wigderson

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


We study non-deterministic communication protocols in which no input has too many witnesses. Define nk(f) to be the minimum complexity of a non-deterministic protocol for the function f in which each input has at most k witnesses. We present two different lower bounds for nk(f). Our first result shows that nk(f) is below by Ω(√c(f)/k), where c(f) is the deterministic complexity. Our second results bounds nk(f) by log(rk(Mf))/k - 1, where rk(Mf) is the rank of the representing matrix of f. As a consequence, 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)
Pages (from-to)247-257
Number of pages11
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Oct 1994

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


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

Cite this