Log-rank conjecture
In theoretical computer science, the log-rank conjecture states that the deterministic communication complexity of a two-party Boolean function is polynomially related to the logarithm of the rank of its input matrix.
Let denote the deterministic communication complexity of a function, and let denote the rank of its input matrix . Since every protocol using up to bits partitions into at most monochromatic rectangles, and each of these has rank at most 1,
The log-rank conjecture states that is also upper-bounded by a polynomial in the log-rank: for some constant,
The best known upper bound, due to Lovett,
states that
The best known lower bound, due to Göös, Pitassi and Watson, states that. In other words, there exists a sequence of functions, whose log-rank goes to infinity, such that
Recently, an approximate version of the conjecture has been disproved.
