Grigoriev, D.; Razborov, A. Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. (English) Zbl 1040.68045 Appl. Algebra Eng. Commun. Comput. 10, No. 6, 465-487 (2000). Summary: 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 depth 3 arithmetic circuits computing some explicit functions \(f\:(F^*)^n\to F\) (in particular, the determinant of a matrix). Cited in 3 ReviewsCited in 19 Documents MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) PDFBibTeX XMLCite \textit{D. Grigoriev} and \textit{A. Razborov}, Appl. Algebra Eng. Commun. Comput. 10, No. 6, 465--487 (2000; Zbl 1040.68045) Full Text: DOI HAL