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.[1][2]
Let [math]\displaystyle{ D(f) }[/math] denote the deterministic communication complexity of a function, and let [math]\displaystyle{ \operatorname{rank}(f) }[/math] denote the rank of its input matrix [math]\displaystyle{ M_f }[/math] (over the reals). Since every protocol using up to [math]\displaystyle{ c }[/math] bits partitions [math]\displaystyle{ M_f }[/math] into at most [math]\displaystyle{ 2^c }[/math] monochromatic rectangles, and each of these has rank at most 1,
- [math]\displaystyle{ D(f) \geq \log_2 \operatorname{rank}(f). }[/math]
The log-rank conjecture states that [math]\displaystyle{ D(f) }[/math] is also upper-bounded by a polynomial in the log-rank: for some constant [math]\displaystyle{ C }[/math],
- [math]\displaystyle{ D(f) = O((\log \operatorname{rank}(f))^C). }[/math]
Lovett [3] proved the upper bound
- [math]\displaystyle{ D(f) = O\left(\sqrt{\operatorname{rank}(f)} \log \operatorname{rank}(f)\right). }[/math]
This was improved by Sudakov and Tomon,[4] who removed the logarithmic factor, showing that
- [math]\displaystyle{ 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,[5] states that [math]\displaystyle{ C \geq 2 }[/math]. In other words, there exists a sequence of functions [math]\displaystyle{ f_n }[/math], whose log-rank goes to infinity, such that
- [math]\displaystyle{ D(f_n) = \tilde\Omega((\log \operatorname{rank}(f_n))^2). }[/math]
In 2019, an approximate version of the conjecture has been disproved.[6]
See also
References
- ↑ 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
- ↑ Lovett, Shachar (February 2014), "Recent advances on the log-rank conjecture in communication complexity", Bulletin of the EATCS 112
- ↑ Lovett, Shachar (March 2016), "Communication is Bounded by Root of Rank", Journal of the ACM 63 (1): 1:1–1:9, doi:10.1145/2724704
- ↑ Sudakov, Benny; Tomon, Istvan (30 Nov 2023). "Matrix discrepancy and the log-rank conjecture". arXiv:2311.18524 [math].
- ↑ 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
- ↑ 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
 |  |
