ECCC-Report TR18-206https://eccc.weizmann.ac.il/report/2018/206Comments and Revisions published for TR18-206en-usMon, 03 Dec 2018 22:54:45 +0200
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