Random Walks on Rotating Expanders

Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost -the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As an example, when G is a d-regular Ramanujan graph, the power graph G t has spectral expansion 2 Ω(t) √ D, where D = d t is the regularity of G t , thus, G t is 2 Ω(t) away from being Ramanujan. This exponential blowup manifests itself in many applications.

In this work we bypass this barrier by permuting the vertices of the given graph after each random step. We prove that there exists a sequence of permutations for which the spectral expansion deteriorates by only a linear factor in t. In the Ramanujan case this yields an expansion of O(t √ D). We stress that the permutations are tailor-made to the graph at hand and require no randomness to generate.

Our proof, which holds for all sufficiently high girth graphs, makes heavy use of the powerful framework of finite free probability and interlacing families that was developed in a seminal sequence of works by Marcus, Spielman and Srivastava.