Shachar Lovett (Theory Seminar)

The log-rank conjecture is a famous conjecture in communication complexity, which also came up in a number of other domains. It asks "what is the structure of low-rank boolean matrices", and gives a precise conjecture for that. Despite many decades of research, the known bounds are still exponentially far from the conjectured ones.

In this talk, I will first introduce this conjecture and what we know of it. Then, I will show that a special case of it arising in combinatorics of set intersection is in fact equivalent to the full conjecture, based on the study of a new notion of matrix rank that we call "signed rank".

Based on joint work with Lianna Hambardzumyan and Morgan Shirley.