Non-deterministic communication complexity with few witnesses

✍ Scribed by Mauricio Karchmer; Ilan Newman; Mike Saks; Avi Wigderson

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 582 KB
• Volume: 49
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(05)80049-2

✦ Synopsis

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 fin 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 bounded below by t2(~-f)/k), where c(f) is the deterministic complexity. Our second results bounds nk(f) by log(rk(M1))/k-1, where rk(M/) is the rank of the representing matrix off 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.