"The structure of protocols for XOR functions"
Kaave Hosseini
(UCSD)
Monday, May 2nd, 2016, 2:00 pm
EBU3B, Room 4258
Abstract:
Let f : {0, 1}^n → {0, 1} be a boolean function. Its associated XOR function is the two party function f⊕(x, y) = f(x ⊕ y). We show that, up to polynomial factors, the deterministic communication complexity of f⊕ is equal to the parity decision tree complexity of f. This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.
Joint work with Hamed Hatami and Shachar Lovett.
Paper Link http://eccc.hpi-web.de/report/2016/044