I know that if we take a random function, it's likely that the maximal fooling set is at most $kn$ for some constant $k$, while the CC is almost $n$. What bound can I get from above on the communication complexity given the maximal fooling set? For example, is it possible that the fooling set is $O(1)$ while the communication complexity is about $n$?

  • $\begingroup$ Fooling set size is a lower bound also for nondeterministic communication complexity. So, the gap you are interested in follows from gaps between det and nondet comm. complexity, and these can be up to n/\log n. See, e.g., this this or this paper. $\endgroup$ – Stasys Jul 2 '17 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.