Skip to main content
Open Access Publications from the University of California

UC San Diego

UC San Diego Previously Published Works bannerUC San Diego

Structure of Protocols for XOR Functions

Published Web Location
No data is associated with this publication.

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.

Item not freely available? Link broken?
Report a problem accessing this item