Revision #1 Authors: Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

Accepted on: 19th February 2019 19:29

Downloads: 851

Keywords:

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$.

TR18-206 Authors: Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

Publication: 3rd December 2018 22:54

Downloads: 1482

Keywords:

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.