39th Annual Symposium on Foundations of Computer Science Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields Palo Alto, California November 08-November 11 ISBN: 0-8186-9172-7
A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field $F$. Also, we study the complexity of the functions $f : D^n \to F$ for subsets $D \subset F$. In particular, we prove an exponential lower bound on the complexity of a depth 3 arithmetic circuit which computes the determinant or the permanent of a matrix considered as functions $f : (F^*)^{n^2} \to F$
Index Terms:
depth 3 arithmetic circuits, exponential lower bounds, approximating by sparse polynomials
Citation:
D. Grigoriev, A. Razborov, "Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields," focs, pp.269, 39th Annual Symposium on Foundations of Computer Science, 1998 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb