Log-rank conjecture
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.<ref>Lovász, László; Saks, Michael (1988), Möbius Functions and Communication Complexity, Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, pp. 81–90{{citation}}: CS1 maint: location missing publisher (link)</ref><ref>Lovett, Shachar (February 2014), "Recent advances on the log-rank conjecture in communication complexity", Bulletin of the EATCS, 112, arXiv:1403.8106</ref>
Let <math>D(f)</math> denote the deterministic communication complexity of a function, and let <math>\operatorname{rank}(f)</math> denote the rank of its input matrix <math>M_f</math> (over the reals). Since every protocol using up to <math>c</math> bits partitions <math>M_f</math> into at most <math>2^c</math> monochromatic rectangles, and each of these has rank at most 1,
- <math>D(f) \geq \log_2 \operatorname{rank}(f). </math>
The log-rank conjecture states that <math>D(f)</math> is also upper-bounded by a polynomial in the log-rank: for some constant <math>C</math>,
- <math>D(f) = O((\log \operatorname{rank}(f))^C). </math>
Lovett <ref>Lovett, Shachar (March 2016), "Communication is Bounded by Root of Rank", Journal of the ACM, 63 (1): 1:1–1:9, arXiv:1306.1877, doi:10.1145/2724704, S2CID 47394799</ref> proved the upper bound
- <math>D(f) = O\left(\sqrt{\operatorname{rank}(f)} \log \operatorname{rank}(f)\right). </math>
This was improved by Sudakov and Tomon,<ref>Sudakov, Benny; Tomon, Istvan (30 Nov 2023). "Matrix discrepancy and the log-rank conjecture". arXiv:2311.18524 [math].</ref> who removed the logarithmic factor, showing that
- <math>D(f) = O\left(\sqrt{\operatorname{rank}(f)}\right). </math>
This is the best currently known upper bound.
The best known lower bound, due to Göös, Pitassi and Watson,<ref>Göös, Mika; Pitassi, Toniann; Watson, Thomas (2018), "Deterministic Communication vs. Partition Number", SIAM Journal on Computing, 47 (6): 2435–2450, doi:10.1137/16M1059369</ref> states that <math>C \geq 2</math>. In other words, there exists a sequence of functions <math>f_n</math>, whose log-rank goes to infinity, such that
- <math> D(f_n) = \tilde\Omega((\log \operatorname{rank}(f_n))^2). </math>
In 2019, an approximate version of the conjecture has been disproved.<ref>Chattopadhyay, Arkadev; Mande, Nikhil; Sherif, Suhail (2019), The Log-Approximate-Rank Conjecture is False, Annual ACM Symposium on the Theory of Computing, Phoenix, Arizona, USA{{citation}}: CS1 maint: location missing publisher (link)</ref>
