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 ${\displaystyle D(f)}$denote the deterministic communication complexity of a function, and let ${\displaystyle \operatorname {rank} (f)}$denote the rank of its input matrix ${\displaystyle M_{f}}$(over the reals). Since every protocol using up to ${\displaystyle c}$bits partitions ${\displaystyle M_{f}}$into at most ${\displaystyle 2^{c}}$monochromatic rectangles, and each of these has rank at most 1,

${\displaystyle D(f)\geq \log _{2}\operatorname {rank} (f).}$

The log-rank conjecture states that ${\displaystyle D(f)}$is also upper-bounded by a polynomial in the log-rank: for some constant ${\displaystyle C}$,

${\displaystyle D(f)=O((\log \operatorname {rank} (f))^{C}).}$

Lovett proved the upper bound

${\displaystyle D(f)=O\left({\sqrt {\operatorname {rank} (f)}}\log \operatorname {rank} (f)\right).}$

This was improved by Sudakov and Tomon, who removed the logarithmic factor, showing that

${\displaystyle D(f)=O\left({\sqrt {\operatorname {rank} (f)}}\right).}$

This is the best currently known upper bound.

The best known lower bound, due to Göös, Pitassi and Watson, states that ${\displaystyle C\geq 2}$. In other words, there exists a sequence of functions ${\displaystyle f_{n}}$, whose log-rank goes to infinity, such that

${\displaystyle D(f_{n})={\tilde {\Omega }}((\log \operatorname {rank} (f_{n}))^{2}).}$

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

• List of unsolved problems in computer science