Non-deterministic communication complexi
โ
Mauricio Karchmer; Ilan Newman; Mike Saks; Avi Wigderson
๐
Article
๐
1994
๐
Elsevier Science
๐
English
โ 582 KB
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 show