Theory of Computing Seminar
February 12, 2016
Structure of protocols for XOR functions
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.
Theory of Computing Seminar Series