Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > EMANUELE VIOLA:
All reports by Author Emanuele Viola:

TR26-251 | 14th October 2026
Chin Ho Lee, Shachar Lovett, Tejas Nareddy, Emanuele Viola

Pseudorandom Bits for Low-Degree Modular Polynomials

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




ISSN 1433-8092 | Imprint