Skip to main content
Structure of Protocols for XOR Functions
Published Web Location
https://eccc.weizmann.ac.il/report/2016/044/revision/1/downloadNo data is associated with this publication.
Abstract
Let f : {0, 1}n → {0, 1} be a boolean function. Its associated XOR function is the two-party function f(x, y) = f(x y). We show that, up to polynomial factors, the deterministic communication complexity of f 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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.