Alphabet-Preserving Lifting for the Log-Rank Conjecture
2026-08-03 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how hard it is to communicate information represented by a Boolean matrix using deterministic communication. They focus on the log-rank conjecture, which relates this difficulty to the logarithm of the matrix's rank. The authors improve previous lower bounds by creating a more efficient matrix construction that makes communication provably harder, using a special lifting technique with a non-Boolean alphabet. They also provide a detailed proof of a key technical tool (the multicolor simulation theorem) needed for their argument.
Boolean communication matrixdeterministic communication complexitylog-rank conjecturematrix ranklower boundspointer functionIndex gadgetmulticolor simulation theoremalphabet liftingcommunication complexity
Authors
Zhao Song
Abstract
For a Boolean communication matrix $M$, let $D(M)$ denote its deterministic communication complexity and let $r(M):={\mathrm{rank}}_{\mathbb{R}}(M)$. The log-rank conjecture asks whether $D(M)$ is polynomial in $\log r(M)$. The best known general upper bound, due to Sudakov and Tomon'25, is $D(M)=O(\sqrt{r(M)})$. On the lower-bound side, G{ö}{ö}s, Pitassi, and Watson'18 constructed explicit matrices satisfying $D(M)=Ω((\log r(M))^2/(\log\log r(M))^2)$. We improve the lower bound to $D(M)=Ω((\log r(M))^2/\log\log r(M))$. Our construction revisits their pointer function over its original non-Boolean alphabet and lifts it with an alphabet-valued Index gadget, via the multicolor simulation theorem stated by Roughgarden and Weinstein'16. Compared with the quantitatively explicit GPW bound, the alphabet-preserving lift removes one factor of $\log\log r$. We also give a self-contained proof of the multicolor simulation theorem in the parameter regime required by the construction.