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 formula_1 denote the deterministic communication complexity of a function, and let formula_2 denote the rank of its input matrix formula_3 (over the reals). Since every protocol using up to formula_4 bits partitions formula_3 into at most formula_6 monochromatic rectangles, and each of these has rank at most 1,
The log-rank conjecture states that formula_1 is also "upper-bounded" by a polynomial in the log-rank: for some constant formula_9,
The best known upper bound, due to Lovett,
states that
The best known lower bound, due to Göös, Pitassi and Watson, states that formula_12. In other words, there exists a sequence of functions formula_13, whose log-rank goes to infinity, such that
Recently, an approximate version of the conjecture has been disproved.