1 Answers
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 {\displaystyle D} denote the deterministic communication complexity of a function, and let rank {\displaystyle \operatorname {rank} } denote the rank of its input matrix M f {\displaystyle M_{f}} . 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,
The log-rank conjecture states that D {\displaystyle D} is also upper-bounded by a polynomial in the log-rank: for some constant C {\displaystyle C} ,
The best known upper bound, due to Lovett,states that