Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-206 | 3rd December 2018 17:37

Equality Alone Does Not Simulate Randomness

RSS-Feed




TR18-206
Authors: Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Publication: 3rd December 2018 22:54
Downloads: 164
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