The log-rank conjecture

Is deterministic communication complexity polylogarithmic in the rank of the communication matrix?

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Let $f : X \times Y \to \{0,1\}$ and let $M_f$ be its communication matrix over the reals. Conjecture: the deterministic communication complexity satisfies

D(f) = (\log \operatorname{rank} M_f)^{O(1)}.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Posed by Lovász and Saks in 1988. The lower bound $D(f) \ge \log \operatorname{rank} M_f$ is immediate; the conjecture asks whether the gap is at most polynomial.

Why it matters

It is a clean test of whether algebraic rank captures communication, and equivalent formulations connect it to the Boolean function analysis programme, to graph colouring of the corresponding rank-bounded structures, and to circuit depth via Karchmer–Wigderson games.

Known partial results

Lovett (2016) proved $D(f) = O(\sqrt{r}\log r)$ where $r = \operatorname{rank} M_f$ ; Sudakov and Tomon later removed the log factor, giving $O(\sqrt{r})$ .
The best known separation is $D(f) = \tilde{\Omega}((\log r)^{2})$ , from a construction of Göös, Pitassi and Watson building on Nisan–Wigderson.
So the truth lies between $(\log r)^2$ and $\sqrt r$ , a gap of exponential size.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.