Partitioning to Sumsets Vs. Subspaces via Entropy Decrement

Let f:F_2^n --> {0,1} be a function and suppose F_2^n x F_2^n is partitioned into k sets A_i x B_i such that f is constant on each sumset A_i + B_i.  We show this implies a partitioning of F_2^n to quasipoly(k) affine subspaces such that f is constant on each. In other words, up to polynomial factors, deterministic communication complexity and parity decision tree complexity of f are equal. This relies on a novel technique of entropy decrement combined with Sanders' Bogolyubov-Ruzsa lemma.

Joint work with Hamed Hatami and Shachar Lovett.