Oszukiwanie dowolnych funkcji symetrycznych

Mówi się, że rozkład ϵ -fooluje funkcję f if | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Mówi się, że oszuka klasę funkcji, jeśli oszuka każdą funkcję w tej klasie. Wiadomym jest, że ε -biased obowiązuje oszukać klasę parytetów nad podzbiorów. (patrz Alon-Goldreich-Hastad-Peralta$\mathcal{D}$$\epsilon$$f$$|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$

$\epsilon$dla niektórych ładnych konstrukcji takich przestrzeni). Pytanie, które chcę zadać, dotyczy uogólnienia tego na dowolne funkcje symetryczne.

Pytanie: Załóżmy, że bierzemy klasę dowolnych funkcji symetrycznych nad pewnym podzbiorem, czy mamy rozkład (z niewielkim wsparciem), który oszuka tę klasę?

Kilka małych obserwacji:

• Wystarczy oszukać dokładne progi ( wynosi 1 wtedy i tylko wtedy, gdy x ma dokładnie k jednych spośród indeksów w S ). Dowolny rozkład że ε -fools tych dokładnych wartości progowe zostaną n ε oszukać wszystkie funkcje symetrycznych na N bitów. (Jest tak, ponieważ każdą funkcję symetryczną można zapisać jako rzeczywistą liniową kombinację tych dokładnych progów, gdzie współczynniki w kombinacji wynoszą 0 lub 1. Liniowość oczekiwań daje nam wtedy to, czego chcemy) . Podobny argument działa również w przypadku progów ogólnych ( Th S k ( $\text{ETh}^S_k(x)$$x$$k$$S$$\epsilon$$n\epsilon$$n$
  
  wynosi 1 wtedy i tylko wtedy, gdy x ma co najmniej k spośród indeksów w S )$\text{Th}^S_k(x)$$x$$k$$S$

• Istnieje wyraźna konstrukcja dystrybucji z obsługą za pośrednictwem PRG Nisana dla LOGSPACE .$n^{O(\log n)}$

• Arbitralne -strony niezależne nie będą działać. Na przykład, jeżeli S jest zbiorem wszystkich x tak, że liczba zer w X jest niezerowe mod 3, jest to rzeczywiście ε -biased bardzo małych ε (z powodu Arkadev Chattopadyay ). Ale najwyraźniej nie oszuka to funkcji MOD3.$\epsilon$$S$$x$$\epsilon$$\epsilon$

Ciekawym podproblemem może być: załóżmy, że chcemy po prostu oszukać funkcje symetryczne we wszystkich indeksach n , czy mamy niezłą przestrzeń? Z powyższych obserwacji musimy po prostu oszukać funkcje progowe ponad bitami, co jest tylko rodziną funkcji n + 1 . W ten sposób można po prostu wybrać rozkład za pomocą brutalnej siły. Ale czy są ładniejsze przykłady przestrzeni, które oszukują Th [ n ] k dla każdego k ?$n$$n+1$$\text{Th}^{[n]}_k$$k$

Tak, Parikshit Gopalan, Raghu Meka, Omer Reingold i David Zuckerman podali ostatnio ogólne rozwiązanie tego problemu, patrz Pseudorandom Generators for Combinatorial Shapes .

$n$ $\log m$$n$

$p$