Alphabet-Preserving Lifting for the Log-Rank Conjecture

For a Boolean communication matrix $M$, let $D(M)$ denote its deterministic communication complexity and let $r(M):={\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}_{\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{"o}{"o}s, Pitassi, and Watson’18 constructed explicit matrices satisfying $D(M)=\mathrm{\Omega }((\log r(M){)}^2\mathrm{/}(\log \log r(M){)}^2)$. We improve the lower bound to $D(M)=\mathrm{\Omega }((\log r(M){)}^2\mathrm{/}\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.