ECCC-Report TR18-206https://eccc.weizmann.ac.il/report/2018/206Comments and Revisions published for TR18-206en-usTue, 19 Feb 2019 19:29:10 +0200
Revision 1
| Equality Alone Does Not Simulate Randomness |
Arkadev Chattopadhyay,
Shachar Lovett,
Marc Vinyals
https://eccc.weizmann.ac.il/report/2018/206#revision1The 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.Tue, 19 Feb 2019 19:29:10 +0200https://eccc.weizmann.ac.il/report/2018/206#revision1
Paper TR18-206
| Equality Alone Does Not Simulate Randomness |
Arkadev Chattopadhyay,
Shachar Lovett,
Marc Vinyals
https://eccc.weizmann.ac.il/report/2018/206The 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. Mon, 03 Dec 2018 22:54:45 +0200https://eccc.weizmann.ac.il/report/2018/206