Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-024 | 25th June 2022 21:06

Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs

RSS-Feed




Revision #1
Authors: Louis Golowich, Salil Vadhan
Accepted on: 25th June 2022 21:06
Downloads: 53
Keywords: 


Abstract:

We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. A line of prior work has shown that random walks on expanders with second largest eigenvalue $\lambda$ fool symmetric functions up to a $O(\lambda)$ error in total variation distance, but only for the case where the vertices are labeled with symbols from a binary alphabet, and with a suboptimal dependence on the bias of the labeling. We generalize these results to labelings with an arbitrary alphabet, and for the case of binary labelings we achieve an optimal dependence on the labeling bias. We extend our analysis to unify it with and strengthen the expander-walk Chernoff bound. We then show that expander walks fool permutation branching programs up to a $O(\lambda)$ error in $\ell_2$-distance, and we prove that much stronger bounds hold for programs with a certain structure. We also prove lower bounds to show that our results are tight. To prove our results for symmetric functions, we analyze the Fourier coefficients of the relevant distributions using linear-algebraic techniques. Our analysis for permutation branching programs is likewise linear-algebraic in nature, but also makes use of the recently introduced singular-value approximation notion for matrices (Ahmadinejad et al. 2021).



Changes to previous version:

Improvements to presentation.


Paper:

TR22-024 | 17th February 2022 23:58

Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs





TR22-024
Authors: Louis Golowich, Salil Vadhan
Publication: 20th February 2022 10:20
Downloads: 327
Keywords: 


Abstract:

We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. We show that expander walks fool symmetric functions up to a $O(\lambda)$ error in total variation distance. This bound improves upon a line of prior work, which gave bounds that were weaker or applied only in more restricted cases. We extend our analysis to unify it with and strengthen the expander walk Chernoff bound. We then show that expander walks fool permutation branching programs up to a $O(\lambda)$ error in $\ell_2$-distance, and we prove that much tighter bounds hold for programs with a certain structure. We also prove lower bounds to show that our results are tight. To prove our results for symmetric functions, we analyze the Fourier coefficients of the relevant distributions using linear-algebraic techniques. Our analysis for permutation branching programs is likewise linear-algebraic in nature, but also makes use of the recently introduced singular-value approximation notion for matrices (Ahmadinejad et al. 2021).



ISSN 1433-8092 | Imprint