Nondeterministic Communication Complexity of Random Boolean Functions

Abstract

We study nondeterministic communication complexity and related concepts (fooling sets, fractional covering number) of random functions $f:X\times Y\to \{0,1\}$ where each value is chosen to be 1 independently with probability $p=p(n)$, $n:=|X|=|Y|$.

Version with proofs (in the appendix). Extended abstract appeared in Proceedings of Theory and Applications of Models of Computation, TAMC, 2016