D. Grigoriev et A. Razborov, Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields, APPL ALG EN, 10(6), 2000, pp. 465-487
Citations number
18
Categorie Soggetti
Engineering Mathematics
Journal title
APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING
A depth 3 arithmetic circuit can be viewed as a sum of products of linear f
unctions. We prove an exponential complexity lower bound on depth 3 arithme
tic circuits computing some natural symmetric functions over a finite field
F. Also, we study the complexity of the functions f : D-n --> F for subset
s D subset of F, In particular, we prove an exponential lower bound on the
complexity of depth 3 arithmetic circuits computing some explicit functions
f: (F*)(n) --> F (in particular, the determinant of a matrix).