Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DEPTH-4 CIRCUITS:
Reports tagged with depth-4 circuits:
TR12-098 | 3rd August 2012
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

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

Revisions: 3

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

TR13-091 | 17th June 2013
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

#### A super-polynomial lower bound for regular arithmetic formulas.

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>

ISSN 1433-8092 | Imprint