Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)

摘要

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