# Fooling arbitrary symmetric functions

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$?

• Maybe this comment can help. Linial and Nisan's conjecture has recently been settled by Mark Braverman. The title of the paper is "Polylogarithmic independence fools AC^0 circuits". cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf Commented Jan 16, 2011 at 3:06

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.
• But Gopalan-Meka-Reingold-Zuckerman do not give an optimal PRG for inverse polynomial error right? For a constant $\varepsilon$, it is optimal though. Nevertheless, thank you very much for the pointer. Commented Feb 19, 2011 at 13:31
• Indeed they don't. In general that's a difficult goal, and there are relatively few instances in the literature in which a logarithmic dependence on $\epsilon$ is achieved.