Nondeterministic Communication Complexity of Random Boolean Functions

2016/11/25 by Mozhgan Pourmoradnasseri, Pourmoradnasseri, Mozhgan, Dirk Oliver Theis +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.1611.08400

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

arxiv created 2016/12/02 · arxiv updated 2016/12/05

Abstract

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

Related

• Pseudodeterministic Communication Complexity
• Probabilistic communication complexity over the reals
• Explicit separations between randomized and deterministic Number-on-Forehead communication
• A study of distributional complexity measures for Boolean functions
• A discrepancy lower bound for information complexity