For a $\{0,1\}$-valued matrix $M$ let CC$(M)$ denote the deterministic communication complexity of the boolean function associated with $M$. It is well-known since the work of Mehlhorn and Schmidt [STOC 1982] that CC$(M)$ is bounded from above by rank$(M)$ and from below by $\log$ rank $(M)$ where rank$(M)$ denotes the rank of $M$ over the field of real numbers. Determining where in this range lies the true worst-case value of CC$(M)$ is a fundamental open problem in communication complexity. The state of the art is \[\log^{1.631} \mbox{ rank} (M)\leq \mbox{CC}(M) \leq 0.415\ \mbox{ rank}(M),\] the lower bound is by Kushilevitz [unpublished, 1995] and the upper bound is due to Kotlov [Journal of Graph Theory, 1996]. Lov\'{a}sz and Saks [FOCS 1988] conjecture that CC$(M)$ is closer to the lower bound, i.e., CC$(M)\leq \log^c(\mbox{ rank}(M))$ for some absolute constant $c$ --- this is the famous ``log-rank conjecture'' --- but so far there has been no evidence to support it, even giving a slightly non-trivial ($o(\mbox{rank}(M))$) upper bound on the communication complexity.

Our main result is that, assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, there exists a universal constant $c$ such that \[\mbox{CC}(M)\leq c \cdot \mbox{rank}(M)/\log \mbox{rank}(M).\] Although our bound is stated using the rank of $M$ over the reals, our proof goes by studying the problem over the finite field of size $2$, and there we bring to bear a number of new tools from additive combinatorics which we hope will facilitate further progress on this perplexing question.

In more detail, our proof is based on the study of the ``approximate duality conjecture'' which was suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get our upper bound on the communication complexity of low-rank matrices.

Modified title, abstract, introduction and Section 4. Proofs and main claims remain unchanged.

For a {0,1}-valued matrix $M$ let CC($M$) denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field of real numbers.

We show that CC($M$) is at most $c \cdot \mbox{rank}(M)/\log \mbox{rank}(M)$ for some absolute constant $c$, assuming a well-known conjecture from additive combinatorics known as the Polynomial Freiman-Ruzsa (PFR) conjecture.

Our proof is based on the study of the "approximate duality conjecture" which was recently suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, where this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995].