Nondeterministic Communication Complexity of Random Boolean Functions
classification
💻 cs.DM
cs.CC
keywords
communicationcomplexityfunctionsnondeterministicrandombooleanchosencolon
read the original abstract
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|$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.