An exponential lower bound for depth 3 arithmetic circuits

Abstract

We 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.