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 $D(f)$ denote the deterministic communication complexity of a function, and let $\operatorname(f)$ denote the rank of its input matrix $M_f$ (over the reals). Since every protocol using up to $c$ bits partitions $M_f$ into at most $2^c$ monochromatic rectangles, and each of these has rank at most 1,
:$D(f) \geq \log_2 \operatorname(f).$
The log-rank conjecture states that $D(f)$ is also ''upper-bounded'' by a polynomial in the log-rank: for some constant $C$,
:$D(f) = O((\log \operatorname(f))^C).$

The best known upper bound, due to Lovett,
states that
:$D(f) = O\left(\sqrt \log \operatorname(f)\right).$

The best known lower bound, due to Göös, Pitassi and Watson, states that $C \geq 2$. In other words, there exists a sequence of functions $f_n$, whose log-rank goes to infinity, such that
:$D(f_n) = \tilde\Omega((\log \operatorname(f_n))^2).$

Recently, an approximate version of the conjecture has been disproved.

References

{{reflist

Communication
Computational complexity theory
Conjectures
Unsolved problems in computer science