Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin
Neeraj Kayal, Chandan Saha · Computational Complexity · 2016
Shpilka & Wigderson (IEEE conference on computational complexity, vol 87, 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 & Wigderson (Comp Complex 6(3):217–234, 1997) had posed the problem of proving super-polynomial lower bounds for homogeneous depth-five arithmetic circuits. Over fields of characteristic zero, 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}$$ ).