# On the Pseudo-Mixing of Kac's Walk

arXiv: https://arxiv.org/abs/2608.17374 · HTML: https://mlsanity.com/paper/2608.17374/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 46 references that are in the map.
- First posted on arXiv 18 Aug 2026.

## Builds on (most cited first, 7 of 7)

- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [The Fast Johnson-Lindenstrauss Transform is Even Faster](https://mlsanity.com/paper/2204.01800/) (2022)
- [Function-Specific Mixing Times and Concentration Away from Equilibrium](https://mlsanity.com/paper/1605.02077/) (2016)
- [Practical Secure Delegated Linear Algebra with Trapdoored Matrices](https://mlsanity.com/paper/2502.13060/) (2025)
- [Optimal Fast Johnson-Lindenstrauss Embeddings for Large Data Sets](https://mlsanity.com/paper/1712.01774/) (2017)
- [The Quasi-Polynomial Low-Degree Conjecture is False](https://mlsanity.com/paper/2505.17360/) (2025)
- [A Sparse Johnson-Lindenstrauss Transform using Fast Hashing](https://mlsanity.com/paper/2305.03110/) (2023)

## Abstract (arXiv)

Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on SO(n): whether short trajectories are indistinguishable from Haar measure by low-complexity tests. We prove that the first k columns mix in Wasserstein distance in O(n(k+log n)log n) steps for fixed accuracy, resolving a conjecture of Oliveira. Combining this with a representation-theoretic variance bound, we show that if T=ω(nk(k+log n)log n), then every degree-k polynomial normalized to have unit Haar variance has expectation under the T-step law within o(1) of its Haar expectation. As an application, we show that this pseudo-mixing estimate can be used to prove the effectiveness of a fast Johnson--Lindenstrauss transform with the usual target dimension.