TR99-023 Authors: Amir Shpilka, Avi Wigderson

Publication: 16th June 1999 12:08

Downloads: 1001

Keywords:

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.