Theory of Computing Seminar

Friday, February 12, 2016

12:00pm to 1:00pm

Annenberg 213

Structure of protocols for XOR functions

Shachar Lovett, UCSD,

Abstract:

Communication complexity studies the structure of optimal communication protocols. Even in the simplest case of deterministic two-party protocols, the structure of optimal protocols is unknown. For example, the famous log rank conjecture postulates that the communication cost is related to the rank of an associated matrix.

In this work, we study XOR functions: two players receive inputs x,y in F_2^n, and their goal is to compute f(x + y), where f:F_2^n \to F_2 is a boolean function. A natural way to construct such a protocol is to simulate a parity decision tree for f. This is a decision tree model, where each node is allowed to query a linear function of the input. A parity decision tree of depth d gives a communication protocol with 2d communication.

Our main result is establishing the reverse direction: any protocol which sends c bits, implies a parity decision tree with depth poly(c). Our proof technique differs from most "simulation" techniques in communication complexity: we do not argue about individual rectangles, but instead about the structure of the entire protocol. Our result also sheds some light on quantitative differences between coloring and density versions of structural results in additive combinatorics.

Joint work with Kaave Hosseini.

For more information, please contact Thomas Vidick by email at [email protected].

Event Series

Theory of Computing Seminar Series

Event Sponsors

Computing and Mathematical Sciences (CMS) More Events from this Sponsor