Engañar funciones simétricas arbitrarias

Se dice que una distribución ϵ -engaña una función f si | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Y se dice que engaña a una clase de funciones si engaña a todas las funciones de esa clase. Se sabe que la varepsilon espacios -biased engañar a la clase de las paridades sobre subconjuntos. (ver Alon-Goldreich-Hastad-Peralta$\mathcal{D}$$\epsilon$$f$$|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$

$\epsilon$para algunas buenas construcciones de tales espacios). La pregunta que quiero hacer es una generalización de esto a funciones simétricas arbitrarias.

Pregunta: Supongamos que tomamos la clase de funciones simétricas arbitrarias sobre algún subconjunto, ¿tenemos una distribución (con poco soporte) que engañe a esta clase?

Algunas pequeñas observaciones:

• Es suficiente engañar los umbrales exactos ( es 1 si y solo si x tiene exactamente k unos entre los índices en S ). Cualquier distribución que ε -fools estos umbrales exactos será n ε engañar a todas las funciones simétricas sobre n bits. (Esto se debe a que cada función simétrica se puede escribir como una combinación lineal real de estos umbrales exactos donde los coeficientes en la combinación son 0 o 1. La linealidad de la expectativa nos da lo que queremos) Un argumento similar también funciona para umbrales generales ( Th S k ( $\text{ETh}^S_k(x)$$x$$k$$S$$\epsilon$$n\epsilon$$n$
  
  es 1 si y solo si x tiene al menos k unos entre los índices en S )$\text{Th}^S_k(x)$$x$$k$$S$

• Hay una construcción explícita de una distribución con soporte través de PRG de Nisan para LOGSPACE .$n^{O(\log n)}$

• Los espacios arbitrarios imparciales no funcionarán. Por ejemplo, si S es el conjunto de todos los x tales que el número de unos en x no es cero mod 3, esto es en realidad ε -biased para muy pequeño ε (a partir de un resultado de Arkadev Chattopadyay ). Pero claramente esto no engaña a la función MOD3.$\epsilon$$S$$x$$\epsilon$$\epsilon$

Un subproblema interesante puede ser el siguiente: supongamos que solo queremos engañar a las funciones simétricas en todos los n índices , ¿tenemos un buen espacio? Según las observaciones anteriores, solo necesitamos engañar las funciones de umbral sobre bits, que es solo una familia de funciones n + 1 . Por lo tanto, uno puede elegir la distribución por fuerza bruta. ¿Pero hay mejores ejemplos de espacios que engañan a Th [ n ] k 's por cada k ?$n$$n+1$$\text{Th}^{[n]}_k$$k$

Sí, recientemente Parikshit Gopalan, Raghu Meka, Omer Reingold y David Zuckerman han dado una solución general a este problema, ver Generadores pseudoaleatorios para formas combinatorias .

Ese papel maneja una configuración aún más general, donde el generador genera bloques log m -bit, que luego se alimentan a funciones booleanas arbitrarias, cuyas n salidas se alimentan a una función simétrica booleana.$n$ $\log m$$n$

Ya se conocía una variedad de sub-casos; véanse, por ejemplo, los generadores de bits pseudoaleatorios que engañan a las sumas modulares , los medios espacios de tontos de independencia limitados y los generadores pseudoaleatorios para las funciones de umbral polinomial . El primero maneja sumas módulo . El segundo y el tercero manejan con precisión las pruebas de umbral que menciona, sin embargo, el error no es lo suficientemente bueno como para aplicar su razonamiento para obtener un resultado para cada función simétrica.$p$