# Just how bad is the fooling set method in communication complexity?

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$?

• 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. – Stasys Jul 2 '17 at 12:16