H.B. Keller Colloquium

Determining the mixing time of Kac's random walk on the n-sphere was a long-standing open problem. In this talk, I will discuss my joint work with Aaron Smith on obtaining the optimal mixing time bounds for this talk and its variants. In addition to discussing the key coupling construction underlying our proof, I will discuss its connections and applications to random matrix theory, dimension reduction methods, and other statistical applications. In particular, we will exhibit a Johnson-Lindenstrauss (JL) transform using Kac's walk that is memory-optimal and outperforms existing algorithms in certain regimes, confirming a conjecture of Ailon and Chazelle. No background on mixing times is assumed.

This is joint work with Aaron Smith, Vishesh Jain, Ashwin Sah, Mehtaab Sawhney