Pseudorandomness of Expander Walks via Fourier Analysis on Groups
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915400727396352 |
|---|---|
| author | Jeronimo, Fernando Granha Mittal, Tushant Roy, Sourya |
| author_facet | Jeronimo, Fernando Granha Mittal, Tushant Roy, Sourya |
| contents | One approach to study the pseudorandomness properties of walks on expander graphs is to label the vertices of an expander with elements from an alphabet $Σ$, and study the mean of functions over $Σ^n$. We say expander walks $\varepsilon$-fool a function if, for any unbiased labeling of the vertices, the expander walk mean is $\varepsilon$-close to the true mean. We show that:
- The class of symmetric functions is $O(|Σ|\cdotλ)$-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(|Σ|)}\cdot λ)$, by Golowich and Vadhan [CCC'22]. Additionally, if the expander is a Cayley graph over $\mathbb{Z}_{|Σ|}$, we get a further improved bound of $O(\sqrt{|Σ|}\cdotλ)$.
Morever, when $Σ$ is a finite group $G$, we show the following for functions over $G^n$:
- The class of symmetric class functions is $O\Big({\frac{\sqrt{|G|}}{D}\cdotλ}\Big)$-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 $\mathbb{Z}_2$ or $\mathbb{Z}$. This enables us to get quantitatively better bounds even for unstructured sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14445 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pseudorandomness of Expander Walks via Fourier Analysis on Groups Jeronimo, Fernando Granha Mittal, Tushant Roy, Sourya Computational Complexity Discrete Mathematics Combinatorics One approach to study the pseudorandomness properties of walks on expander graphs is to label the vertices of an expander with elements from an alphabet $Σ$, and study the mean of functions over $Σ^n$. We say expander walks $\varepsilon$-fool a function if, for any unbiased labeling of the vertices, the expander walk mean is $\varepsilon$-close to the true mean. We show that: - The class of symmetric functions is $O(|Σ|\cdotλ)$-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(|Σ|)}\cdot λ)$, by Golowich and Vadhan [CCC'22]. Additionally, if the expander is a Cayley graph over $\mathbb{Z}_{|Σ|}$, we get a further improved bound of $O(\sqrt{|Σ|}\cdotλ)$. Morever, when $Σ$ is a finite group $G$, we show the following for functions over $G^n$: - The class of symmetric class functions is $O\Big({\frac{\sqrt{|G|}}{D}\cdotλ}\Big)$-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 $\mathbb{Z}_2$ or $\mathbb{Z}$. This enables us to get quantitatively better bounds even for unstructured sets. |
| title | Pseudorandomness of Expander Walks via Fourier Analysis on Groups |
| topic | Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2507.14445 |