Modular gates are known to be immune for the random
restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and
Hastad. We demonstrate here a random clustering technique which
overcomes this difficulty and is capable to prove generalizations of
several known modular circuit lower bounds of Barrington, Straubing,
Therien; Krause ... more >>>

We revisit the problem of constructing explicit pseudorandom generators which output $n$ bits that look random to $n$-variate degree-$d$ polynomials modulo $m$. We give new generators with seed length $2^{O(dm^2)} \log(n/\varepsilon)$, which is optimal for any fixed $m$ and $d$. Along the way, we prove new Fourier growth bounds for ... more >>>