@inproceedings{ca161c8bd7ba4d45833db60f72e734f1,
title = "{"}Resistant{"} polynomials and stronger lower bounds for depth-three arithmetical formulas",
abstract = "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.",
keywords = "Arithmetical circuits, Computational complexity, Constant depth formulas, Lower bounds, Partial derivatives",
author = "Jansen, \{Maurice J.\} and Regan, \{Kenneth W.\}",
year = "2007",
doi = "10.1007/978-3-540-73545-8\_46",
language = "English",
isbn = "9783540735441",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "470--481",
booktitle = "Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings",
address = "Germany",
note = "13th Annual International Computing and Combinatorics Conference, COCOON 2007 ; Conference date: 16-07-2007 Through 19-07-2007",
}