The log-rank conjecture

The deterministic communication complexity of a boolean function \(f\) is bounded by a polynomial in the logarithm of the rank of its communication matrix: \(cc(f) \le (\log \mathrm{rank}(M_f))^{O(1)}\).

Formulated in the late 1980s (Lovász–Saks) at the birth of communication complexity (Yao 1979). The rank lower bound is one of the few completely general tools, so the conjecture asks whether it is essentially the only obstruction. Lovett (2016) proved communication is bounded by roughly the square root of the rank — the first bound sublinear in the rank — and Göös–Pitassi–Watson (2018) separated deterministic communication from partition number, showing some neighbouring conjectures fail even if log-rank holds. The polynomial version stands open.