BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Structure of protocols for XOR functions Lovett, Shachar


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International