STOC Conference 1992 Conference Paper
Randomized versus Nondeterministic Communication Complexity
- Paul Beame
- Joan Lawry
Our main result is the demonstration of a Boolean function f with nondeterministic and co-nondeterministic complexities O (log n ) and ε-error randomized complexity Ω(log 2 n ), for 0 ≤ ε < 1/2. This is the first separation of this kind for a decision problem.