Nondeterministic Communication Complexity of Random Boolean Functions
  We study nondeterministic communication complexity and related concepts (fooling sets, fractional covering number) of random functions $f\colon X\times Y \to \{0,1\}$ where each value is chosen to be 1 independently with probability $p=p(n)$, $n := |X|=|Y|$. 
Mozhgan Pourmoradnasseri and Dirk Oliver Theis
cs.DM cs.CC