Open Collections

Description

Let f be a boolean function on n variables. Its associated XOR function is the two-party function F(x, y) = f(x xor y). If f has a parity decision tree of depth d, then it gives a natural deterministic protocol for F which sends 2d bits. We establish the reverse direction: any deterministic protocol for F which sends c bits, implies a parity decision tree for f of depth poly(c). The proof combines a novel technique of entropy reduction for protocols, with existing techniques in Fourier analysis and additive combinatorics. Joint work with Hamed Hatami and Kaave Hosseini.