"Resistant" Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas.

We derive quadratic lower bounds on the *-complexity of sum-of-products-of-sums (ΣΠΣ) formulas for classes of polynomials f that have too few partial derivatives for the techniques of Shpilka and Wigderson [10,9]. This involves a notion of "resistance" which connotes full-degree behavior of f under any projection to an affine space of sufficiently high dimension. They also show stronger lower bounds over the reals than the complex numbers or over arbitrary fields. Separately, by applying a special form of the Baur-Strassen Derivative Lemma tailored to ΣΠΣ formulas, we obtain sharper bounds on + ,*-complexity than those shown for *-complexity by Shpilka and Wigderson [10], most notably for the lowest-degree cases of the polynomials they consider. [ABSTRACT FROM AUTHOR]