New advances on the log rank conjecture

The log rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the simplest lower bound for deterministic protocols, the log-rank lower bound, is in fact tight up to polynomial factors. That is, for a boolean function f(x,y), if its associated matrix M_{x,y}=f(x,y) has rank r (over the reals), then there exists a deterministic protocol computing f which uses only poly-log(r) bits of communication. This problem also has several other equivalent formulations: the relation between chromatic number and rank of graphs, and the relation between rank and non-negative rank for boolean matrices. A simple argument shows that there is always a deterministic protocol which uses r bits of communication, and until recently the best known bounds improved on this only by a constant factor. Recently, two new approaches allowed for improved bounds. The first (joint with Eli Ben-Sasson and Noga Ron-Zewi) related it to a central conjecture in additive number theory, and showed that if it holds then there are protocols which use O(r / log(r)) bits. The second approach is analytical and gives an (unconditional) improved upper bound of O(\sqrt{r} \log(r)) bits of communication. In the talk I will give the necessary background on the problem, explain the two approaches, sketch the proofs, and discuss intriguing connections to other central problems in complexity theory, such as matrix rigidity and two-source extractors.