Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Random Walks on Rotating Expanders
event speaker icon
Irit Dinur (Weizmann Institute of Science) & Gil Cohen (Tel-Aviv university)
event date icon
Wednesday, 30.11.2022, 12:30
event location icon
Taub 201
Random walks on expanders are extremely useful in TOC. Unfortunately though, they have an inherent cost. E.g., the spectral expansion of a Ramanujan graph deteriorates exponentially with the length of the walk (when compared to a Ramanujan graph of the same degree). In this talk, we will see how this exponential cost can be reduced to linear by applying a permutation after each random step. These permutations are tailor-made to the graph at hand, requiring no randomness to generate. Our proof is established using the powerful framework of finite free probability and interlacing families that was introduced, around ten years ago, by Marcus, Spielman, and Srivastava in their seminal sequence of works on the existence of bipartite Ramanujan graphs of every size and every degree, and in their solution to the Kadison-Singer problem. Joint work with Gal Maor.