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

Structure of protocols for XOR functions

  • Author(s): Hatami, H
  • Hosseini, K
  • Lovett, S
  • et al.

Published Web Location

https://eccc.weizmann.ac.il/report/2016/044/revision/1/download
No data is associated with this publication.
Abstract

© 2018 Society for Industrial and Applied Mathematics. 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