In a recent breakthrough, Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola (ECCC'26) established exponential correlation bounds for polynomials over $\mathbf{F}_2$ and, as a consequence, obtained a major improvement in PRG constructions for low-degree polynomials over the binary field. In particular, they obtained seed length $\widetilde{O}(d^2\log^2 n)$ for fooling degree-$d$ polynomials in $n$ variables with constant error.

Our main contribution is to achieve the optimal dependence on the number of variables $n$, at the expense of a polynomial deterioration in the dependence on $d$. Specifically, we obtain seed length $O(d^4\log n)$, as well as a bound of $\widetilde{O}(d^3\log n)$. We also obtain nearly linear dependence on $\log(1/\varepsilon)$, improving the quadratic dependence in the Fourier-based PRG of Chattopadhyay et al.

Finally, we show that a random walk on a $\lambda$-spectral expander fools degree-$d$ polynomials over $\mathbf{F}_2$ with error $O(d^2\lambda)$, provided that the labeling is balanced. The bound is independent of the walk length $n$. To prove this, we extend the Fourier-analytic approach of Cohen, Peri, and Ta-Shma (STOC '21), replacing level-wise bounds on the Fourier $L_1$ mass with bounds that account for cancellations among coefficients within each level.