Equality Alone Does not Simulate Randomness
Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
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.