Nondeterministic communication with a limited number of advice bits
Juraj Hromkovic̆, Georg Schnitger · 1996
We present a new technique to differentiate deterministic from nondeterministic communication complexity.As a consequence we give almost tight lower bounds for the nondeterministic communication complexity with a restricted number of advice bits (i.e., nondeterministic guesses).In particular, for any function t : N + N (with t(k) < k/2) we construct a family (L~,t(k) : m c N) of languages such that (a) L~,,f~J'~{O, I} 'k, (b) ncc,(~)(L,,,(k)) = O(t(k)), (c) nc%, k(bc,t(k)) = 0("~k ), (d) but IIC%(t(k)/ bg2 k)(~k,t(k)) = '( Iog2(,&t(k)) )" (ncc, (L) is the nondeterministic communication complexity of L, assuming that at most r advice bits are used for any input.) Thus, in contrast to probabilistic communication complexity, a small reduction in the number of advice bits results in almost maximal communication, even if the original number of advice bits is super-logarithmic.