Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SYMMETRIC FUNCTION:
Reports tagged with Symmetric function:
TR99-023 | 16th June 1999
Amir Shpilka, Avi Wigderson

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero


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 ... more >>>




ISSN 1433-8092 | Imprint