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.

Improved lower bound from \Omega(n/\log n) to \Omega(n) and added a new result about a hierarchy within BPP.

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.