<p>Yes, a general solution to this problem has recently been given by
Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman,
see <a href="http://eccc.uni-trier.de/report/2010/176/" rel="nofollow">Pseudorandom Generators for Combinatorial Shapes</a>.</p>

<p>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.</p>

<p>A variety of sub-cases were already known; see for example <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.157.8574" rel="nofollow">Pseudorandom Bit Generators That Fool Modular Sums</a>, <a href="http://eccc.hpi-web.de/report/2009/016/" rel="nofollow">Bounded Independence Fools Halfspaces</a>, and <a href="http://arxiv.org/abs/0910.4122" rel="nofollow">Pseudorandom Generators for Polynomial Threshold Functions</a>. 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.</p>

CC BY-SA 2.5
2011-02-19T13:31:03.850Z
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.
Ramprasad
CC BY-SA 2.5
2011-02-19T14:43:38.307Z
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.
Manu
CC BY-SA 2.5
2011-02-16T23:39:46.150Z
2011-02-17T19:01:10.297Z
2011-02-17T19:01:10.297Z
Manu
<p>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. <br><br>
It is known that $\epsilon$-biased spaces fool the class of parities over subsets. (see <a href="http://www.wisdom.weizmann.ac.il/~oded/p_aghp.html">Alon-Goldreich-Hastad-Peralta</a> for some nice constructions of such spaces). The question I want to ask is a generalization of this to arbitrary symmetric functions. </p>

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

<p>Some small observations: </p>

<ul>
<li><p>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)<br><br>
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$)</p></li>
<li><p>There is an explicit construction of a distribution with support $n^{O(\log n)}$ via <a href="http://www.cs.huji.ac.il/~noam/sc.ps">Nisan's PRG for LOGSPACE</a>. </p></li>
<li><p>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 <a href="http://www.eccc.uni-trier.de/report/2006/107/">result of Arkadev Chattopadyay</a>).   But clearly this does not fool the MOD3 function. </p></li>
</ul>

<p>An interesting subproblem may be the following: suppose we just want to fool symmetric functions over <em>all n indices</em>, 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$? </p>

CC BY-SA 2.5
2011-01-16T03:06:29.503Z
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". 


 http://www.cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf
Mirmojtaba Gharibi
<cc.complexity-theory><derandomization><space-bounded><pseudorandomness>
Fooling arbitrary symmetric functions
Ramprasad
# Fooling arbitrary symmetric functions

(Asked by: username_0 on 2010-10-13)

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](http://www.wisdom.weizmann.ac.il/~oded/p_aghp.html) 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](http://www.cs.huji.ac.il/~noam/sc.ps).
* 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](http://www.eccc.uni-trier.de/report/2006/107/)). 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$?

**Tags:** cc.complexity-theory, derandomization, space-bounded, pseudorandomness
> **Comments:**
> **username_1**: 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".     http://www.cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf  

---

## 1 answers

### Answer by username_2 on 2011-02-16. Score: 11 | Accepted answer

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](http://eccc.uni-trier.de/report/2010/176/).

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.157.8574), [Bounded Independence Fools Halfspaces](http://eccc.hpi-web.de/report/2009/016/), and [Pseudorandom Generators for Polynomial Threshold Functions](http://arxiv.org/abs/0910.4122). 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  

---

