Pseudorandomness of the Sticky Random Walk

Author: Anand, Emile Timothy

Year: 2023

Degree: Senior thesis (Major)

Advisor: Umans, Christopher M.

Committee Member: None, None

Option: Computer Science

DOI: 10.7907/ze1k-6v37

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 pp 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(λ pp) 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.

Files