Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields
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