Beyond the Worst Case: Structured Convergence of High Dimensional Random Walks
share
One of the most important properties of high dimensional expanders is that high dimensional random walks converge rapidly. This property has proven to be extremely useful in variety of fields in the theory of computer science from agreement testing to sampling, coding theory and more. In this paper we improve upon the result of Kaufman-Oppenheim and Alev-Lau regarding the convergence of random walks by presenting a structured version of their result. While previous works examined the expansion in the viewpoint of the worst possible eigenvalue, in this work we relate the expansion of a function to the entire spectrum of the random walk operator using the structure of the function. In some cases this finer result can be much better than the worst case. In order to prove our structured version of the convergence of random walks, we present a general framework that allows us to relate the convergence of random walks to the trickling down theorem for the first time. Concretely, we show that both the state of the art results for convergence of random walks and the tricking down theorem can be derived using the same argument that we present here. This new, unified, way of looking at the convergence of high dimensional random walks and the trickling down theorem gives us a new understanding of pseudorandom functions that allows us to consider pseudorandom functions in one-sided local spectral expanders for the first time.
READ FULL TEXT