Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-127 | 24th July 2026 10:56

Approximating Polynomials for De Morgan Formulas with Optimal Coefficient L1-Norm Bounds

RSS-Feed




TR26-127
Authors: Yichuan Wang
Publication: 24th July 2026 15:05
Downloads: 23
Keywords: 


Abstract:

We prove that every De Morgan formula with $n$ leaves has a pointwise $1/3$-approximating real polynomial of degree $O(\sqrt n)$ and coefficient $\ell_1$-norm $2^{O(\sqrt n)}$. The standard approximate-degree theorem for formulas gives the same degree bound, but only yields the weaker coefficient estimate $2^{O(\sqrt n\log n)}$.

Our proof constructs, for every formula, a span program with witness size $O(\sqrt n)$ and, additionally, $O(1)$ entrywise-absolute operator norm for the available-vector matrix. A standard span-program-to-polynomial argument then gives the desired approximating polynomial while preserving coefficient weight.
We also show that the coefficient bound is tight up to constants in the exponent: the De Morgan formula for inner product modulo $2$ already gives a matching $2^{\Omega(\sqrt n)}$ lower bound for formulas with at most $n$ leaves, even regardless of the degree of the approximating polynomial.



ISSN 1433-8092 | Imprint