Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-206 | 19th February 2019 19:29

Equality Alone Does Not Simulate Randomness

RSS-Feed




Revision #1
Authors: Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Accepted on: 19th February 2019 19:29
Downloads: 105
Keywords: 


Abstract:

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on $n$ bits with randomized one-sided communication complexity $O(\log n)$, but such that every deterministic protocol with access to `Equality' oracle needs $\Omega(n)$ cost to compute it.

Additionally we exhibit a natural and strict infinite hierarchy within $BPP$, starting with the class $P^{EQ}$ at its bottom.



Changes to previous version:

Improved lower bound from $\Omega(n/\log n)$ to $\Omega(n)$ and added a new result about a hierarchy within $BPP$.


Paper:

TR18-206 | 3rd December 2018 17:37

Equality Alone Does Not Simulate Randomness





TR18-206
Authors: Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Publication: 3rd December 2018 22:54
Downloads: 370
Keywords: 


Abstract:

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on $n$ bits with randomized one-sided communication complexity $O(\log n)$, but such that every deterministic protocol with access to `Equality' oracle needs $\Omega(n/\log n)$ cost to compute it.



ISSN 1433-8092 | Imprint