Shachar Lovett: The log-rank conjecture - where do we stand?

The log-rank conjecture is one of the tantalizing open problems in communication complexity. Initiated by Lovasz and Saks in 1988, it speculates that any binary matrix of low rank has an efficient communication protocol; equivalently, that it can be partitioned into a small number of monochromatic rectangles. Despite over 30 years of research, we are still very far from resolving it.

In this talk, I will describe recent progress on the log-rank conjecture. In particular, I will discuss progress on special cases, called lifted functions, which have surprising connections to the analysis of boolean functions; and a refutation of an extension of the log-rank conjecture to randomized communication.

The talk will assume no background knowledge in communication complexity.