Este artículo investiga la pseudorandomidad de los caminos en grafos expandentes utilizando análisis de Fourier en grupos. Se basa en trabajos anteriores que han estudiado este tema para diversas funciones, como la función XOR y la función AND.
**Resultados Clave**:
* **Funciones Simétricas**: El artículo muestra que las funciones simétricas son engañadas por caminos expandentes de cualquier λ-expander genérico y cualquier alfabeto Σ en O(|Σ|λ). Esto generaliza los resultados anteriores para |Σ| = 2 y mejora exponencialmente el límite anterior de O(|Σ| O(|Σ|) λ).
* **Grupos Finitos**: Cuando Σ es un grupo finito G, el artículo muestra que la clase de funciones simétricas es engañada por caminos expandentes sobre "estructurados" λ-expandentes en O(√|G| D λ) si G es D-quasirandom. Esto proporciona un límite más fuerte que el resultado anterior para expanders genéricos.
* **Límites Inferiores**: El artículo demuestra un límite inferior de Ω(λ) para las funciones simétricas para cualquier grupo finito G, incluso para "estructurados" λ-expandentes. Esto demuestra que hay un límite fundamental a cuánto se puede mejorar la pseudorandomidad de los caminos expandentes.
* **Funciones No Simétricas**: El artículo estudia el espectro de Fourier de una clase de funciones no simétricas que surgen de los mapas de palabras y muestra que son engañadas exponencialmente por caminos expandentes.
**Técnicas de Prueba**:
El artículo utiliza análisis de Fourier sobre grupos generales, lo que contrasta con los trabajos anteriores que han estudiado tanto el caso de Z2 como el de Z. Esto permite al artículo obtener límites cuantitativamente mejores incluso para conjuntos no estructurados.
**Significación**:
Este artículo contribuye a nuestra comprensión de la pseudorandomidad de los grafos expandentes y sus aplicaciones en informática y matemáticas. Proporciona nuevos límites e insights sobre el comportamiento de los caminos expandentes y su capacidad para engañar funciones. El artículo también destaca el poder del análisis de Fourier como herramienta para estudiar la pseudorandomidad en grafos.
**Puntos Adicionales**:
* El artículo utiliza un "gráfico pseudo Cayley" para obtener límites mejorados para funciones con simetría de grupo.
* El artículo proporciona un límite inferior para el engaño de funciones simétricas, incluso sobre "gráficos pseudo Cayley".
* El artículo muestra que la pseudorandomidad de un grupo puede utilizarse para mejorar los límites para los caminos expandentes.