A Caltech Library Service

Pseudorandomness of the Sticky Random Walk


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


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.

Item Type:Thesis (Senior thesis (Major))
Subject Keywords:pseudorandomness, expander random walks, sticky random walk, Krawtchouk functions
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Umans, Christopher M.
Group:Caltech Theory
Thesis Committee:
  • None, None
Defense Date:11 June 2023
Non-Caltech Author Email:emiletimothy (AT)
Record Number:CaltechTHESIS:06142023-102020321
Persistent URL:
Anand, Emile Timothy0000-0003-2893-9469
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:16116
Deposited By: Emile Anand
Deposited On:15 Jun 2023 22:13
Last Modified:08 Nov 2023 18:51

Thesis Files

[img] PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page