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  (over the reals). 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

In 2019, an approximate version of the conjecture has been disproved.

See also 

 List of unsolved problems in computer science

References

Communication
Computational complexity theory
Conjectures
Unsolved problems in computer science
Information theory