Revision #2 Authors: Mrinal Kumar, Shubhangi Saraf

Accepted on: 13th January 2015 14:52

Downloads: 693

Keywords:

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 {\it 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^{O(1)}$ must have size $n^{\Omega(\sqrt{n})}$.

Our results strengthen previous works in two significant ways.

Our lower bounds hold for a polynomial in $VP$. Prior to our work, Kayal et al [KLSS14] 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^{\Omega(\log n)}$ by [KLSS, KLSS14]. 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).

Our lower bound holds over all fields. The lower bound of [KLSS14] 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^{\Omega(\log n)}$ [KLSS, KLSS14].

Revision #1 Authors: Mrinal Kumar, Shubhangi Saraf

Accepted on: 12th January 2015 17:54

Downloads: 765

Keywords:

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 {\it 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^{O(1)}$ must have size $n^{\Omega(\sqrt{n})}$.

Our results strengthen previous works in two significant ways.

Our lower bounds hold for a polynomial in $VP$. Prior to our work, Kayal et al [KLSS14] 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^{\Omega(\log n)}$ by [LSS, KLSS14]. 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).

Our lower bound holds over all fields. The lower bound of [KLSS14] 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^{\Omega(\log n)}$ [LSS, KLSS14].

Updated a reference

TR14-045 Authors: Mrinal Kumar, Shubhangi Saraf

Publication: 7th April 2014 23:19

Downloads: 2067

Keywords:

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 {\it 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^{O(1)}$ must have size $n^{\Omega(\sqrt{n})}$.

Our results strengthen previous works in two significant ways.

Our lower bounds hold for a polynomial in $VP$. Prior to our work, Kayal et al [KLSS14] 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^{\Omega(\log n)}$ by [LSS, KLSS14]. 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).

Our lower bound holds over all fields. The lower bound of [KLSS14] 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^{\Omega(\log n)}$ [LSS, KLSS14].