An additive combinatorics approach to the log-rank conjecture in communication complexity

Eli Ben-Sasson, Shachar Lovett, Noga Zewi

For a $\{0,1\}$-valued matrix $M$ let $\mathrm{CC}(\mathrm{M})$ denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovász…