2026-08-11T07:52:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24415 2025-12-12T15:01:39Z ddc:004 open_access

Pseudorandomness of Expander Walks via Fourier Analysis on Groups Jeronimo, Fernando Granha Mittal, Tushant Roy, Sourya Expander graphs pseudorandomness A long line of work has studied the pseudorandomness properties of walks on expander graphs. A central goal is to measure how closely the distribution over n-length walks on an expander approximates the uniform distribution of n-independent elements. One approach to do so is to label the vertices of an expander with elements from an alphabet Σ, and study closeness of the mean of functions over Σⁿ, under these two distributions. We say expander walks ε-fool a function if the expander walk mean is ε-close to the true mean. There has been a sequence of works studying this question for various functions, such as the XOR function, the AND function, etc. We show that: - The class of symmetric functions is O(|Σ|λ)-fooled by expander walks over any generic λ-expander, and any alphabet Σ . This generalizes the result of Cohen, Peri, Ta-Shma [STOC'21] which analyzes it for |Σ| = 2, and exponentially improves the previous bound of O(|Σ|^O(|Σ|) λ), by Golowich and Vadhan [CCC'22]. Moreover, if the expander is a Cayley graph over ℤ_|Σ|, we get a further improved bound of O(√{|Σ|} λ). Morever, when Σ is a finite group G, we show the following for functions over Gⁿ: - The class of symmetric class functions is O({√|G|}/D λ}-fooled by expander walks over "structured" λ-expanders, if G is D-quasirandom. - We show a lower bound of Ω(λ) for symmetric functions for any finite group G (even for "structured" λ-expanders). - We study the Fourier spectrum of a class of non-symmetric functions arising from word maps, and show that they are exponentially fooled by expander walks. Our proof employs Fourier analysis over general groups, which contrasts with earlier works that have studied either the case of ℤ₂ or ℤ. This enables us to get quantitatively better bounds even for unstructured sets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fernando Granha Jeronimo and Tushant Mittal and Sourya Roy 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.49 urn:nbn:de:0030-drops-244157 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.49 eng https://creativecommons.org/licenses/by/4.0/legalcode