Log-rank conjecture explained

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).}

Lovettproved the upper bound

D(f) = O\left(\sqrt{\operatorname{rank}(f)} log \operatorname{rank}(f)\right). This was improved by Sudakov and Tomon,^[1] who removed the logarithmic factor, showing thatD(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 thatD(f _{n)} = \tilde\Omega(( log \operatorname{rank}(f ^{2 ).} _{n))}

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

See also

• List of unsolved problems in computer science

Notes and References

1. Sudakov . Benny . Benny Sudakov . Tomon . Istvan . 30 Nov 2023 . Matrix discrepancy and the log-rank conjecture . 2311.18524 . math.