Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Structure of protocols for XOR functions

RSS-Feed




Revision #1
Authors: Hamed Hatami, Kaave Hosseini, Shachar Lovett
Accepted on: 8th April 2016 04:00
Downloads: 4136
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
Downloads: 3223
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.



ISSN 1433-8092 | Imprint