Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1999 Copyright 1999 Universität Bonn, Institut für Informatik, Abt. V
85202

An Exponential Lower Bound for Depth 3 Arithmetic Circuits
Dima Grigoriev, Marek Karpinski
[Download PostScript] [Download PDF]

We prove the first exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the {\em determinant}) over an arbitrary finite field. This answers an open problem of \cite{N91} and \cite{NW95} for the case of finite fields. We intepret here arithmetic circuits in the algebra of polynomials over the given field. The proof method involves a new argument on the rank of linear functions, and a group symmetry on polynomials vanishing at certain nonsingular matrices, and could be of independent interest.

Last Change: 07/05/01 at 14:03:02
 English
Universität Bonn -> Institut für Informatik -> Abteilung V