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]

Unsolved problem in computer science: Prove or disprove the log rank conjecture. (more unsolved problems in computer science)

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

${\displaystyle D(f)\geq \log _{2}\operatorname {rank} (f).}$

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

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

The best known upper bound, due to Lovett,[3] states that

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

The best known lower bound, due to Göös, Pitassi and Watson,[4] states that ${\displaystyle C\geq 2}$. In other words, there exists a sequence of functions ${\displaystyle f_{n}}$, whose log-rank goes to infinity, such that

${\displaystyle D(f_{n})={\tilde {\Omega }}((\log \operatorname {rank} (f_{n}))^{2}).}$

Recently, an approximate version of the conjecture has been disproved.[5]