Misplaced Pages

Log-rank conjecture

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Unsolved problem in theoretical computer science

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.

See also

References

  1. 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)
  2. Lovett, Shachar (February 2014), "Recent advances on the log-rank conjecture in communication complexity", Bulletin of the EATCS, 112, arXiv:1403.8106
  3. 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
  4. Sudakov, Benny; Tomon, Istvan (30 Nov 2023). "Matrix discrepancy and the log-rank conjecture". arXiv:2311.18524 .
  5. 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
  6. 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)
Categories: