ECCC-Report TR12-098https://eccc.weizmann.ac.il/report/2012/098Comments and Revisions published for TR12-098en-usWed, 04 Sep 2013 10:06:36 +0300
Revision 3
| Approaching the chasm at depth four |
Ankit Gupta,
Pritish Kamath,
Neeraj Kayal,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2012/098#revision3Agrawal-Vinay (FOCS 2008), Koiran (TCS 2012) and Tavenas (MFCS 2013) have recently shown that an $\exp(\omega(\sqrt{n}\log n))$ lower bound for depth four homogeneous circuits computing the permanent with bottom layer of $\times$ gates having fanin bounded by $\sqrt{n}$ translates to super-polynomial lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin.
We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by $\sqrt{n}$ computing the permanent (or the determinant) must be of size $\exp(\Omega(\sqrt{n}))$.Wed, 04 Sep 2013 10:06:36 +0300https://eccc.weizmann.ac.il/report/2012/098#revision3
Revision 2
| Approaching the chasm at depth four |
Ankit Gupta,
Pritish Kamath,
Neeraj Kayal,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2012/098#revision2Agrawal-Vinay (FOCS 2008) and Koiran (TCS 2012) have recently shown that an $\exp(\omega(\sqrt{n}\log^2 n))$ lower bound for depth four homogeneous circuits computing the permanent with bottom layer of $\times$ gates having fanin bounded by $\sqrt{n}$ translates to super-polynomial lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin.
We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by $\sqrt{n}$ computing the permanent (or the determinant) must be of size $\exp(\Omega(\sqrt{n}))$.Sat, 23 Mar 2013 08:10:02 +0200https://eccc.weizmann.ac.il/report/2012/098#revision2
Revision 1
| Approaching the chasm at depth four |
Ankit Gupta,
Pritish Kamath,
Neeraj Kayal,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2012/098#revision1Agrawal-Vinay (FOCS 2008) and Koiran (TCS 2012) have recently shown that an $\exp(\omega(\sqrt{n}\log^2 n))$ lower bound for depth four homogeneous circuits computing the permanent with bottom layer of $\times$ gates having fanin bounded by $\sqrt{n}$ translates to super-polynomial lower bound for a general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin.
We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by $\sqrt{n}$ computing the permanent (or the determinant) must be of size $\exp(\Omega(\sqrt{n}))$.Mon, 10 Sep 2012 08:22:58 +0300https://eccc.weizmann.ac.il/report/2012/098#revision1
Paper TR12-098
| An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin |
Ankit Gupta,
Pritish Kamath,
Neeraj Kayal,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2012/098Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via homogeneous depth four circuits with bounded bottom fanin.
We show here that any homogeneous depth four arithmetic circuit with bounded bottom fanin computing the permanent (or the determinant) must be of exponential size.Fri, 03 Aug 2012 17:06:13 +0300https://eccc.weizmann.ac.il/report/2012/098