Résumé - Pseudorandomness des walks d'expandeurs par analyse de Fourier sur les groupes

Pseudorandomness des walks d'expandeurs par analyse de Fourier sur les groupes

2025-07-19 02:44:34

{"Fernando Granha Jeronimo","Tushant Mittal","Sourya Roy"}

{cs.CC,cs.DM,math.CO}

Ce document enquête sur la pseudorandomité des walks sur les graphes d'expansion en utilisant l'analyse de Fourier sur les groupes. Il s'appuie sur des travaux précédents qui ont étudié ce sujet pour diverses fonctions, telles que la fonction XOR et la fonction AND. **Résultats Clés** : * **Fonctions Symétriques** : Le document montre que les fonctions symétriques sont trompées par les walks d'expansion O(|Σ|λ) sur tout λ-expander générique et tout alphabet Σ. Cela généralise les résultats précédents pour |Σ| = 2 et améliore exponentiellement la borne précédente de O(|Σ| O(|Σ|) λ). * **Groupes Finis** : Lorsque Σ est un groupe fini G, le document montre que la classe des fonctions symétriques est trompée par les walks d'expansion O(√|G| D λ) sur des λ-expanders "structurés" si G est D-quasirandom. Cela fournit une borne plus forte que le résultat précédent pour les expanders génériques. * **Bornes Inférieures** : Le document prouve une borne inférieure de Ω(λ) pour les fonctions symétriques pour tout groupe fini G, même pour des λ-expanders "structurés". Cela montre qu'il existe une limite fondamentale à l'amélioration de la pseudorandomité des walks d'expansion. * **Fonctions Non-Symétriques** : Le document étudie le spectre de Fourier d'une classe de fonctions non-symétriques issues des cartes de mots et montre qu'elles sont trompées exponentiellement par les walks d'expansion. **Techniques de Preuve** : Le document utilise l'analyse de Fourier sur des groupes généraux, ce qui contraste avec les travaux précédents qui ont étudié soit le cas de Z2 ou Z. Cela permet au document d'obtenir des bornes quantitativement meilleures même pour des ensembles non structurés. **Signification** : Ce document contribue à notre compréhension de la pseudorandomité des graphes d'expansion et de leurs applications en informatique et en mathématiques. Il fournit de nouvelles bornes et des insights sur le comportement des walks d'expansion et leur capacité à tromper des fonctions. Le document met également en lumière le pouvoir de l'analyse de Fourier comme outil pour étudier la pseudorandomité sur les graphes. **Points Supplémentaires** : * Le document utilise un "pseudo graphe de Cayley" pour obtenir des bornes améliorées pour les fonctions avec symétrie de groupe. * Le document fournit une borne inférieure pour la tromperie des fonctions symétriques, même sur des "pseudo graphes de Cayley". * Le document montre que la pseudorandomité d'un groupe peut être utilisée pour améliorer les bornes pour les walks d'expansion.