The Taub Faculty of Computer Science Events and Talks

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.