Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROJECTED SHIFTED PARTIALS:
Reports tagged with Projected Shifted Partials:
TR14-089 | 16th July 2014
Neeraj Kayal, Chandan Saha

#### Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

Revisions: 1

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 ... more >>>

TR20-028 | 27th February 2020
Nikhil Gupta, Chandan Saha, Bhargav Thankey

#### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

We show an $\widetilde{\Omega}(n^{2.5})$ lower bound for general depth four arithmetic circuits computing an explicit $n$-variate degree $\Theta(n)$ multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... more >>>

ISSN 1433-8092 | Imprint