Randomized versus Nondeterministic Communication Complexity

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.

Authors

• Paul Beame
• Joan Lawry

Keywords

No keywords are indexed for this paper.