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 {rank} (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 {rank} (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 {rank} (f))^{C}).$

Lovett proved the upper bound

$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

$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 $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 {rank} (f_{n}))^{2}).$

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

See also

• List of unsolved problems in computer science