Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-089 | 2nd December 2014 03:37

Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

RSS-Feed




Revision #1
Authors: Neeraj Kayal, Chandan Saha
Accepted on: 2nd December 2014 03:37
Downloads: 393
Keywords: 


Abstract:

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for nonhomogeneous) depth three arithmetic circuits with bottom fanin at most $\tau$ computing an explicit $N$-variate polynomial of degree $d$ over $\mathbb{F}$.


Meanwhile, Nisan and Wigderson (FOCS 1995) had posed the problem of proving superpolynomial lower bounds for homogeneous depth five arithmetic circuits. We show a lower bound of $N^{\Omega(\sqrt{d})}$ for homogeneous depth five circuits (resp. also for depth three circuits) with bottom fanin at most $N^{\mu}$, for any fixed $\mu < 1$. This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth five circuit has bottom fanin at most $N$).



Changes to previous version:

A key lemma used in the depth three lower bound was first discovered by Shpilka and Wigderson (CCC 1999) (in the earlier version it was attributed to a much more recent paper). We also include a remark to clarify the choice of parameters.


Paper:

TR14-089 | 16th July 2014 10:01

Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin





TR14-089
Authors: Neeraj Kayal, Chandan Saha
Publication: 16th July 2014 11:08
Downloads: 1148
Keywords: 


Abstract:

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin at most $\tau$ computing an explicit $N$-variate polynomial of degree $d$ over $\mathbb{F}$.


Meanwhile, Nisan and Wigderson (FOCS 1995) had posed the problem of proving superpolynomial lower bounds for homogeneous depth five arithmetic circuits. We show a lower bound of $N^{\Omega(\sqrt{d})}$ for homogeneous depth five circuits (resp. also for depth three circuits) with bottom fanin at most $N^{\mu}$, for any fixed $\mu < 1$. This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth five circuit has bottom fanin at most $N$).



ISSN 1433-8092 | Imprint