ECCC-Report TR99-023https://eccc.weizmann.ac.il/report/1999/023Comments and Revisions published for TR99-023en-usWed, 16 Jun 1999 12:08:29 +0300
Paper TR99-023
| Depth-3 Arithmetic Formulae over Fields of Characteristic Zero |
Amir Shpilka,
Avi Wigderson
https://eccc.weizmann.ac.il/report/1999/023
In this paper we prove near quadratic lower bounds for
depth-3 arithmetic formulae over fields of characteristic zero.
Such bounds are obtained for the elementary symmetric
functions, the (trace of) iterated matrix multiplication, and the
determinant. As corollaries we get the first nontrivial lower
bounds for computing polynomials of constant degree, and a
gap between the power depth-3 arithmetic formulas and depth-4
arithmetic formulas.
The main technical contribution relates the complexity of computing a
polynomial in this model to the wealth of partial derivatives it has
on every affine subspace of small co-dimension. Lower bounds for
related models utilize an algebraic analog of Ne{\v{c}}hiporuk
lower bound on Boolean formulae.
Wed, 16 Jun 1999 12:08:29 +0300https://eccc.weizmann.ac.il/report/1999/023