Pseudorandomness of the Sticky Random Walk

Citation

Anand, Emile Timothy (2023) Pseudorandomness of the Sticky Random Walk. Senior thesis (Major), California Institute of Technology. doi:10.7907/ze1k-6v37. https://resolver.caltech.edu/CaltechTHESIS:06142023-102020321

Abstract

We extend the pseudorandomness of random walks on expander graphs using the sticky random walk. Golowich and Vadhan recently showed that expander random walks can fool all symmetric functions in total variation distance (TVD) up to an O(λ pp) error in total variation distance, where lambda is the second largest eigenvalue of the expander and p is the size of the arbitrary alphabet used to label the vertices. It has been conjectured that the dependency on the p^p term is not tight.

In this paper, we resolve the conjecture in the affirmative for a family of expanders. We present a generalization of Guruswami and Kumar's sticky random walk for which prior results predicts a TVD upper bound of O(λ p^p) using a Fourier analytic approach. For this family of graphs, we use a combinatorial approach involving the Krawtchouk functions to derive a strengthened TVD of O(λ). Furthermore, we present equivalencies between instances of the generalized sticky random walk, and, using linear-algebraic techniques, show that the generalized sticky random walk is an infinite family of expanders.

Thesis Files