<p>By &quot;possible,&quot; the authors mean that one can show that a uniformly random set of <span class="math-container">$\mathsf{poly}(n,M,1/\varepsilon)$</span> strings of length <span class="math-container">$n$</span> is a <span class="math-container">$\varepsilon$</span>-PRG for modular tests with exceedingly high probability, but we do not have explicit constructions. This is tight -- the special case of <span class="math-container">$M=2$</span> is a &quot;small bias distribution&quot; and essentially optimal lower bounds are known, and I'd imagine it isn't hard to get the dependence on <span class="math-container">$M$</span>.</p>
<p>The &quot;nonconstructive probabilistic argument&quot; is classical and is really just Chernoff + union bound -- in fact, the seed length <span class="math-container">$O(\log(nM/\varepsilon))$</span> holds also for the larger class of width-<span class="math-container">$M$</span> read-once branching programs. The general claim is that for a class <span class="math-container">$\mathcal{F}$</span>, there exists a (non-explicit) <span class="math-container">$\varepsilon$</span>-PRG with seed length <span class="math-container">$\log\log(\vert \mathcal{F}\vert)+2\log(1/\varepsilon)+O(1)$</span> for this class (see Proposition 1.2.3 of Hoza's thesis if you want to see the proof, but it really is just Chernoff + union bound). There are at at most <span class="math-container">$M^{2M(n+1)}$</span> such branching programs because there are <span class="math-container">$M\cdot (n+1)$</span> states in the program, and for each state, you can describe the (at most) two transitions via two states in the next layer which has size <span class="math-container">$M$</span>.</p>
<p>I should also mention that better constructions of PRGs for modular tests are known. I'm not entirely sure what the state of the art is, but <a href="https://arxiv.org/abs/1506.04350" rel="nofollow noreferrer">Gopalan, Kane, and Meka</a> obtain a PRG for modular tests with seed length <span class="math-container">$O(\log(Mn/\varepsilon)(\log\log(Mn/\varepsilon))^2)$</span> using somewhat different techniques if I remember correctly.</p>

CC BY-SA 4.0
2023-01-21T18:03:27.043Z
2023-01-21T18:03:27.043Z
Jason Gaitonde
<p>In &quot;Pseudorandom Bit Generators That Fool Modular Sums&quot; by Lovett, Reingold, Trevisan, and Vadhan, the authors focus on fooling arbitrary linear sums of <span class="math-container">$n$</span> bits mod <span class="math-container">$M$</span>, and construct a PRG with seed length <span class="math-container">$O(\log(n) + \log(M/\varepsilon)\log(M \log(1/\varepsilon)))$</span>.</p>
<p>However, in the &quot;Discussion&quot; section, the authors mention that &quot;The natural open problem...is to reduce the seed length further, ideally to <span class="math-container">$O(\log(nM/\varepsilon))$</span>, <em>which can be shown to be possible via a nonconstructive probabilistic argument</em>&quot; (emphasis mine).</p>
<p>I have two questions:</p>
<ul>
<li>What is meant by &quot;possible&quot;? As in, there exists a set of <span class="math-container">$poly(n,M,1/\varepsilon)$</span> many strings that fool all modular tests mod <span class="math-container">$M$</span>, but we don't know how to find those strings efficiently? Or is the given length just the minimum seed length that isn't known to be impossible?</li>
<li>Does anyone know the details of this &quot;nonconstructive probabilistic argument&quot;?</li>
</ul>

<pseudorandom-generators>
Nonconstructive $\log(n)$ seed length PRG for fooling modular tests
Jake
# Nonconstructive $\log(n)$ seed length PRG for fooling modular tests

(Asked by: username_0 on 2023-01-20)

In "Pseudorandom Bit Generators That Fool Modular Sums" by Lovett, Reingold, Trevisan, and Vadhan, the authors focus on fooling arbitrary linear sums of $n$ bits mod $M$, and construct a PRG with seed length $O(\log(n) + \log(M/\varepsilon)\log(M \log(1/\varepsilon)))$.

However, in the "Discussion" section, the authors mention that "The natural open problem...is to reduce the seed length further, ideally to $O(\log(nM/\varepsilon))$, *which can be shown to be possible via a nonconstructive probabilistic argument*" (emphasis mine).

I have two questions:

* What is meant by "possible"? As in, there exists a set of $poly(n,M,1/\varepsilon)$ many strings that fool all modular tests mod $M$, but we don't know how to find those strings efficiently? Or is the given length just the minimum seed length that isn't known to be impossible?
* Does anyone know the details of this "nonconstructive probabilistic argument"?

**Tags:** pseudorandom-generators


---

## 1 answers

### Answer by username_1 on 2023-01-21. Score: 2 | Accepted answer

By "possible," the authors mean that one can show that a uniformly random set of $\mathsf{poly}(n,M,1/\varepsilon)$ strings of length $n$ is a $\varepsilon$-PRG for modular tests with exceedingly high probability, but we do not have explicit constructions. This is tight -- the special case of $M=2$ is a "small bias distribution" and essentially optimal lower bounds are known, and I'd imagine it isn't hard to get the dependence on $M$.

The "nonconstructive probabilistic argument" is classical and is really just Chernoff + union bound -- in fact, the seed length $O(\log(nM/\varepsilon))$ holds also for the larger class of width-$M$ read-once branching programs. The general claim is that for a class $\mathcal{F}$, there exists a (non-explicit) $\varepsilon$-PRG with seed length $\log\log(\vert \mathcal{F}\vert)+2\log(1/\varepsilon)+O(1)$ for this class (see Proposition 1.2.3 of Hoza's thesis if you want to see the proof, but it really is just Chernoff + union bound). There are at at most $M^{2M(n+1)}$ such branching programs because there are $M\cdot (n+1)$ states in the program, and for each state, you can describe the (at most) two transitions via two states in the next layer which has size $M$.

I should also mention that better constructions of PRGs for modular tests are known. I'm not entirely sure what the state of the art is, but [Gopalan, Kane, and Meka](https://arxiv.org/abs/1506.04350) obtain a PRG for modular tests with seed length $O(\log(Mn/\varepsilon)(\log\log(Mn/\varepsilon))^2)$ using somewhat different techniques if I remember correctly.


---

