Log-rank conjecture

Short description: Unsolved problem in theoretical computer science

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 $\mathrm{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)\ge {\log }_2\mathrm{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 \mathrm{rank}(f){)}^C).$

Lovett proved the upper bound

$D(f)=O(\sqrt{\mathrm{rank}(f)}\log \mathrm{rank}(f)).$

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

$D(f)=O\left(\sqrt{\mathrm{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\ge 2$. In other words, there exists a sequence of functions $f_n$, whose log-rank goes to infinity, such that

$D(f_n)=\tilde{\mathrm{\Omega }}((\log \mathrm{rank}(f_n){)}^2).$

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

See also

• List of unsolved problems in computer science