For a {0,1}-valued matrix M let CC(M) denote he deterministic
communication complexity of the boolean function associated with M.
The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that
\(CC(M) <= log^c(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) <= c rank(M)/logrank(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, and
this part uses the methodology suggested by Nisan and Wigderson
[Combinatorica 1995]. This is joint work with Eli Ben-Sasson and
Shachar Lovett.
