ECCC-Report TR14-045https://eccc.weizmann.ac.il/report/2014/045Comments and Revisions published for TR14-045en-usTue, 13 Jan 2015 14:52:28 +0200
Revision 2
| On the power of homogeneous depth 4 arithmetic circuits |
Mrinal Kumar,
Shubhangi Saraf
https://eccc.weizmann.ac.il/report/2014/045#revision2We 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].
Tue, 13 Jan 2015 14:52:28 +0200https://eccc.weizmann.ac.il/report/2014/045#revision2
Revision 1
| On the power of homogeneous depth 4 arithmetic circuits |
Mrinal Kumar,
Shubhangi Saraf
https://eccc.weizmann.ac.il/report/2014/045#revision1We 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].
Mon, 12 Jan 2015 17:54:24 +0200https://eccc.weizmann.ac.il/report/2014/045#revision1
Paper TR14-045
| On the power of homogeneous depth 4 arithmetic circuits |
Mrinal Kumar,
Shubhangi Saraf
https://eccc.weizmann.ac.il/report/2014/045We 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].
Mon, 07 Apr 2014 23:19:05 +0300https://eccc.weizmann.ac.il/report/2014/045