Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR12-098 | 4th September 2013 10:06

#### Approaching the chasm at depth four

Revision #3
Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Accepted on: 4th September 2013 10:06
Keywords:

Abstract:

Agrawal-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}))$.

Changes to previous version:

Includes an upper bound for the dimension of shifted partials of the determinant

Revision #2 to TR12-098 | 23rd March 2013 08:10

#### Approaching the chasm at depth four

Revision #2
Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Accepted on: 23rd March 2013 08:10
Keywords:

Abstract:

Agrawal-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}))$.

Changes to previous version:

The lower bound now works for slightly more general circuits that are sums of polynomials of the form $F(Q_1, \cdots, Q_m)$ where $m = \sqrt{n}$ and $\deg(Q_i) = \sqrt{n}$ (and $F$ can be arbitrary).

Revision #1 to TR12-098 | 10th September 2012 08:22

#### Approaching the chasm at depth four

Revision #1
Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Accepted on: 10th September 2012 08:22
Keywords:

Abstract:

Agrawal-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}))$.

Changes to previous version:

Earlier version gave an exponential bound only for constant bottom fan-in. This is a substantial improvement and takes us very close to the chasm.

### Paper:

TR12-098 | 3rd August 2012 09:39

#### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin

TR12-098
Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Publication: 3rd August 2012 17:06
Agrawal 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.