Log-rank conjecture

{{Short description|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.{{citation

| author1-link = László Lovász

| last1 = Lovász | first1 = László

| last2 = Saks | first2 = Michael

| title = Möbius Functions and Communication Complexity

| series = Annual Symposium on Foundations of Computer Science

| place = White Plains, New York, USA

| pages = 81–90

| year = 1988

}}{{citation

| last1 = Lovett | first1 = Shachar

| title = Recent advances on the log-rank conjecture in communication complexity

| journal = Bulletin of the EATCS

| volume = 112

| date = February 2014

| arxiv = 1403.8106

}}

Let $D(f)$ denote the deterministic communication complexity of a function, and let $\backslash operatorname\{rank\}(f)$ denote the rank of its input matrix $M\_f$ (over the reals). Since every protocol using up to $c$ bits partitions $M\_f$ into at most $2^c$ monochromatic rectangles, and each of these has rank at most 1,

:$D(f)\; \backslash geq\; \backslash log\_2\; \backslash operatorname\{rank\}(f).$

The log-rank conjecture states that $D(f)$ is also upper-bounded by a polynomial in the log-rank: for some constant $C$,

:$D(f)\; =\; O((\backslash log\; \backslash operatorname\{rank\}(f))^C).$

Lovett

{{citation

| last1 = Lovett | first1 = Shachar

| title = Communication is Bounded by Root of Rank

| journal = Journal of the ACM

| volume = 63

| issue = 1

| date = March 2016

| pages = 1:1–1:9

| doi = 10.1145/2724704

| arxiv = 1306.1877

| s2cid = 47394799

}}

proved the upper bound

:$D(f)\; =\; O\backslash left(\backslash sqrt\{\backslash operatorname\{rank\}(f)\}\; \backslash log\; \backslash operatorname\{rank\}(f)\backslash right).$

This was improved by Sudakov and Tomon,{{cite arXiv

| last1 = Sudakov

| first1 = Benny

| author-link1 = Benny Sudakov

| last2 = Tomon

| first2 = Istvan

| date = 30 Nov 2023

| title = Matrix discrepancy and the log-rank conjecture

| eprint = 2311.18524

| class = math

}} who removed the logarithmic factor, showing that

:$D(f)\; =\; O\backslash left(\backslash sqrt\{\backslash operatorname\{rank\}(f)\}\backslash right).$

This is the best currently known upper bound.

The best known lower bound, due to Göös, Pitassi and Watson,{{citation

| author2-link = Toniann Pitassi

| last1 = Göös | first1 = Mika

| last2 = Pitassi | first2 = Toniann

| last3 = Watson | first3 = Thomas

| title = Deterministic Communication vs. Partition Number

| journal = SIAM Journal on Computing

| volume = 47

| issue = 6

| pages = 2435–2450

| year = 2018

| doi = 10.1137/16M1059369 }} states that $C\; \backslash geq\; 2$. In other words, there exists a sequence of functions $f\_n$, whose log-rank goes to infinity, such that

:$D(f\_n)\; =\; \backslash tilde\backslash Omega((\backslash log\; \backslash operatorname\{rank\}(f\_n))^2).$

In 2019, an approximate version of the conjecture for randomised communication has been disproved.{{citation

| title = The Log-Approximate-Rank Conjecture is False

| last1 = Chattopadhyay | first1 = Arkadev

| last2 = Mande | first2 = Nikhil

| last3 = Sherif | first3 = Suhail

| series = Annual ACM Symposium on the Theory of Computing

| place = Phoenix, Arizona, USA

| year = 2019

}}