Equality Alone Does not Simulate Randomness Article Swipe

View

Related Concepts

Randomness Oracle Class (philosophy) Randomized algorithm Mathematics Communication complexity Hierarchy Exponential function Function (biology) Discrete mathematics Deterministic algorithm Computer science Theoretical computer science Statistics Artificial intelligence Evolutionary biology Market economy Software engineering Biology Economics Mathematical analysis

Arkadev Chattopadhyay , Shachar Lovett , Marc Vinyals ·

YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.4230/lipics.ccc.2019.14 · OA: W2912462513

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.