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

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

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

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

Lovett proved the upper bound

D ( f ) = O ( rank ⁡ ( f ) log ⁡ rank ⁡ ( f ) ) . {\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

D ( f ) = O ( rank ⁡ ( f ) ) . {\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 C ≥ 2 {\displaystyle C\geq 2} . In other words, there exists a sequence of functions f n {\displaystyle f_{n}} , whose log-rank goes to infinity, such that

D ( f n ) = Ω ~ ( ( log ⁡ rank ⁡ ( f n ) ) 2 ) . {\displaystyle D(f_{n})={\tilde {\Omega }}((\log \operatorname {rank} (f_{n}))^{2}).}

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