Loading jsMath...
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: 1101
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: 1788
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