Oliveira’s Kac-walk mixing conjecture

Oliveira’s conjecture concerns how quickly the first $k$ columns of Kac’s walk approach their random limit; the relevant work of Oliveira appeared in 2009. The associated Vaikuntanathan–Zamir conjecture is broader, asking for computational indistinguishability from Haar randomness.

August 2026 claimed proof

A new preprint claims that the $k$-column walk mixes in Wasserstein distance after $O(n\log n\cdot\max(k,\log n))$ steps, uniformly in $n$ and $k$. It further claims that degree-$k$ real polynomials cannot distinguish Haar-random matrices from walks of approximately $\widetilde{O}(nk^2)$ steps, and derives a fast Johnson–Lindenstrauss transform with an extra logarithmic factor. This resolves Oliveira’s conjecture and the low-degree version of the Vaikuntanathan–Zamir problem if the proof is correct, but no independent verification or reported error assessment was found.

Current status (as of August 2026): Oliveira’s column-mixing conjecture is claimed proved by a new preprint, but remains unverified; the broader Vaikuntanathan–Zamir conjecture remains open.