On the Power of Homogeneous Depth 4 Arithmetic Circuits

Abstract

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in VP. Our results hold for the Iterated Matrix Multiplication polynomial - in particular we show that any homogeneous depth 4 circuit computing the (1, 1) entry in the product of n generic matrices of dimension n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> must have size n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ω(√n)</sup> . Our results strengthen previous works in two significant ways. 1) Our lower bounds hold for a polynomial in VP. Prior to our work, Kayal et al [KLSSa] proved an exponential lower bound for homogeneous depth 4 circuits (over fields of characteristic zero) computing a poly in VNP. The best known lower bounds for a depth 4 homogeneous circuit computing a poly in VP was the bound of n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ω(log n)</sup> by [KLSSb], [KLSSa]. Our exponential lower bounds also give the first exponential separation between general arithmetic circuits and homogeneous depth 4 arithmetic circuits. In particular they imply that the depth reduction results of Koiran [Koi12] and Tavenas [Tav13] are tight even for reductions to general homogeneous depth 4 circuits (without the restriction of bounded bottom fanin). 2) Our lower bound holds over all fields. The lower bound of [KLSSa] worked only over fields of characteristic zero. Prior to our work, the best lower bound for homogeneous depth 4 circuits over fields of positive characteristic was n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ω(log n)</sup> [KLSSb], [KLSSa].