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.^[1][2]

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 ^[3] 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,^[4] 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,^[5] 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.^[6]

See also

• List of unsolved problems in computer science