An exponential lower bound for depth 3 arithmetic circuits
Dima Grigoriev, Marek Karpiński · 1998
AbatractWe prove the first exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the determinant) over an arbitrary finite field.This answers an open problem of [N91] and [NW951 for the cs~e 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.