2023/07/18 by Emile Anand, Anand, Emile, Chris Umans +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.0 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #G.3 #Machine Learning and Algorithms #Probability (math.PR) #Spectral Theory (math.SP)
paper · pdf · doi:10.48550/arxiv.2307.11104
openalex publication_date 2023/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We extend the pseudorandomness of random walks on expander graphs using the sticky random walk. Building on prior works, it was recently shown that expander random walks can fool all symmetric functions in total variation distance (TVD) upto an O(λ((p)/(min f))O(p)) error, where λ is the second largest eigenvalue of the expander, p is the size of the arbitrary alphabet used to label the vertices, and min f = minb∈[p] fb, where fb is the fraction of vertices labeled b in the graph. Golowich and Vadhan conjecture that the dependency on the ((p)/(min f))O(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 the sticky random walk for which Golowich and Vadhan predict a TVD upper bound of O(λpO(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 the generalized sticky random walk, and, using linear-algebraic techniques, show that the generalized sticky random walk parameterizes an infinite family of expander graphs.