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 for randomised communication has been disproved.
See also List of unsolved problems in computer science
References