Fooling arbitrary symmetric functions

Question

A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every function in that class.

It is known that $\epsilon$-biased spaces fool the class of parities over subsets. (see Alon-Goldreich-Hastad-Peralta for some nice constructions of such spaces). The question I want to ask is a generalization of this to arbitrary symmetric functions.

Question: Suppose we take the class of arbitrary symmetric functions over some subset, do we have distribution (with small support) that fools this class?

Some small observations:

• It is sufficient to fool exact thresholds ($\text{ETh}^S_k(x)$ is 1 if and only if $x$ has exactly $k$ ones amongst the indices in $S$). Any distribution that $\epsilon$-fools these exact thresholds will $n\epsilon$ fool all symmetric functions over $n$ bits. (This is because every symmetric function can be written as a real linear combination of these exact thresholds where the coefficients in the combination are either 0 or 1. Linearity of expectation then gives us what we want)
  
  A similar argument also works for general thresholds ($\text{Th}^S_k(x)$ is 1 if and only if $x$ has at least $k$ ones amongst the indices in $S$)

• There is an explicit construction of a distribution with support $n^{O(\log n)}$ via Nisan's PRG for LOGSPACE.

• Arbitrary $\epsilon$-biased spaces will not work. For example if $S$ is the set of all $x$ such that the number of ones in x is non-zero mod 3, this is actually $\epsilon$-biased for very small $\epsilon$ (from a result of Arkadev Chattopadyay). But clearly this does not fool the MOD3 function.

An interesting subproblem may be the following: suppose we just want to fool symmetric functions over all n indices, do we have a nice space? By the above observations, we just need to fool the threshold functions over $n$-bits, which is just a family of $n+1$ functions. Thus one can just pick the distribution by brute-force. But are there nicer examples of spaces that fool $\text{Th}^{[n]}_k$'s for every $k$?

Answer 1

Yes, a general solution to this problem has recently been given by Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman, see Pseudorandom Generators for Combinatorial Shapes.

That paper handles an even more general setting, where the generator outputs $n$ $\log m$-bit blocks, which are then fed to arbitrary boolean functions, whose $n$ outputs are then fed to a boolean symmetric function.

A variety of sub-cases were already known; see for example Pseudorandom Bit Generators That Fool Modular Sums, Bounded Independence Fools Halfspaces, and Pseudorandom Generators for Polynomial Threshold Functions. The first handles sums modulo $p$. The second and the third handle precisely the threshold tests you mention, however the error is not good enough to apply your reasoning to obtain a result for every symmetric function.