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.

Authors

• Gil Cohen
• Gal Maor

Keywords

• expander graphs
• finite free probability
• interlacing families
• random walks on graphs
• spectral graph theory