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 Gt has spectral expansion 2Ω(t) √D, where D = dt is the regularity of Gt, thus, Gt is 2Ω(t) away from being Ramanujan. This exponential blowup manifests itself in many applications.