# Theory of Computing Seminar

Friday
February 12, 2016
12:00 PM

**Structure of protocols for XOR functions**

**Speaker:**Shachar Lovett, UCSD

**Location:**Annenberg 213

**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.

**Series**Theory of Computing Seminar Series

**Contact:** Thomas Vidick vidick@cms.caltech.edu