Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR16-044 | 8th April 2016 04:00

#### Structure of protocols for XOR functions

Revision #1
Authors: Hamed Hatami, Kaave Hosseini, Shachar Lovett
Accepted on: 8th April 2016 04:00
Keywords:

Abstract:

Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.
We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.
This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.

### Paper:

TR16-044 | 21st March 2016 07:00

#### Structure of protocols for XOR functions

TR16-044
Authors: Kaave Hosseini, Shachar Lovett
Publication: 21st March 2016 15:30
Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.
We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.