Error reduction procedures play a crucial role in constructing weighted PRGs [PV'21, CDRST'21], which are central to many recent advances in space-bounded derandomization. The fundamental method driving error reduction procedures is the Richardson iteration, which is adapted from the literature on fast Laplacian solvers. In the context of space-bounded derandomization, where time is not the primary concern, can additional insights from optimization theory lead to improved error reduction procedures?

The results of this paper reveal an inherent barrier for using optimization-based techniques for error reduction in the context of space-bounded derandomization. To this end, we develop an abstract framework for error reduction based on polynomials which in particular encompasses all optimization-based error reduction techniques, and consequently, puts a limit on constructing improved weighted PRGs based on current approaches. Our work also sheds light on the necessity of negative weights within existing methods.

From the technical viewpoint, we establish lower bounds on various important parameters of error reduction polynomials. This includes a lower bound on the degree $d$ of the polynomial, and an $n^{\Omega(d)}$ lower bound on $L_1$-norm of an $n$-variate polynomial. These lower bounds hold both when there are no "correlations" between different approximations and in the presence of such. A delicate use of these correlations has recently been exploited for constructing improved weighted PRGs for various restricted models [CHLTW'23].