Tromper les fonctions symétriques arbitraires

Une distribution est dit ε -fool une fonction f si | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Et on dit qu'il trompe une classe de fonctions s'il trompe chaque fonction de cette classe. Il est connu que les espaces biaisés ϵ trompent la classe de parités sur les sous-ensembles. (voir Alon-Goldreich-Hastad-Peralta$\mathcal{D}$$\epsilon$$f$$|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$

$\epsilon$pour de belles constructions de tels espaces). La question que je veux poser est une généralisation de ceci à des fonctions symétriques arbitraires.

Question: Supposons que nous prenons la classe des fonctions symétriques arbitraires sur un sous-ensemble, avons-nous une distribution (avec un petit support) qui trompe cette classe?

Quelques petites observations:

• Il suffit de tromper des seuils exacts ( vaut 1 si et seulement si x en a exactement k parmi les indices de S ). Toute distribution que ε -fools ces seuils exacts n ε duper toutes les fonctions symétriques sur n bits de . (C'est parce que chaque fonction symétrique peut être écrite comme une combinaison linéaire réelle de ces seuils exacts où les coefficients de la combinaison sont soit 0 soit 1. La linéarité de l'espérance nous donne alors ce que nous voulons) Un argument similaire fonctionne également pour les seuils généraux ( Th S k ( $\text{ETh}^S_k(x)$$x$$k$$S$$\epsilon$$n\epsilon$$n$
  
  vaut 1 si et seulement si x en a au moins k parmi les indices de S )$\text{Th}^S_k(x)$$x$$k$$S$

• Il existe une construction explicite d'une distribution avec le support via le PRG de Nisan pour LOGSPACE .$n^{O(\log n)}$

• Les espaces arbitraires biaisés ne fonctionneront pas. Par exemple , si S est l'ensemble de tous les x tels que le nombre de ceux de x est mod non nul 3, cela est en fait ε -biased très faible pour ε ( à partir d' un résultat de Arkadev Chattopadyay ). Mais clairement, cela ne trompe pas la fonction MOD3.$\epsilon$$S$$x$$\epsilon$$\epsilon$

Un sous-problème intéressant peut être le suivant: supposons que nous voulons simplement tromper les fonctions symétriques sur tous les n indices , avons-nous un bel espace? Par les observations ci-dessus, nous avons juste besoin de tromper les fonctions de seuil sur bits, qui est juste une famille de n + 1 fonctions. Ainsi, on peut simplement choisir la distribution par force brute. Mais existe-t-il de plus beaux exemples d'espaces qui trompent les Th [ n ] k pour chaque k ?$n$$n+1$$\text{Th}^{[n]}_k$$k$

Oui, une solution générale à ce problème a récemment été donnée par Parikshit Gopalan, Raghu Meka, Omer Reingold et David Zuckerman, voir Générateurs pseudo-aléatoires pour les formes combinatoires .

Ce document gère un paramètre encore plus général, où le générateur génère blocs log m- bits, qui sont ensuite alimentés en fonctions booléennes arbitraires, dont les n sorties sont ensuite alimentées en fonction symétrique booléenne.$n$ $\log m$$n$

Divers sous-cas étaient déjà connus; voir par exemple les générateurs de bits pseudo - aléatoires qui trompent les sommes modulaires , les demi - espaces imbriqués d'indépendance bornée et les générateurs pseudo- aléatoires pour les fonctions de seuil polynomial . Le premier gère les sommes modulo . Le deuxième et le troisième gèrent précisément les tests de seuil que vous mentionnez, mais l'erreur n'est pas suffisante pour appliquer votre raisonnement afin d'obtenir un résultat pour chaque fonction symétrique.$p$