Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR18-206 | 19th February 2019 19:29

#### Equality Alone Does Not Simulate Randomness

Revision #1
Authors: Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Accepted on: 19th February 2019 19:29
Downloads: 170
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)\$ cost to compute it.

Additionally we exhibit a natural and strict infinite hierarchy within \$BPP\$, starting with the class \$P^{EQ}\$ at its bottom.

Changes to previous version:

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

### Paper:

TR18-206 | 3rd December 2018 17:37

#### Equality Alone Does Not Simulate Randomness

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