Approaching the chasm at depth four

Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi

June 2013

Agrawal-Vinay (FOCS 2008) and Koiran (TCS 2012) have recently shown that an exp(√(n) * log^{2} n)) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of gates having fanin bounded by √(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 √(n) computing the permanent (or the determinant) must be of size exp(√(n)) .

Publication type | Inproceedings |

Published in | Conference on Computational Complexity |

Publisher | IEEE IEEE |

Awards | Best Paper Award |

- Efficient Reconstruction of Random Multilinear Formulas
- On the Sum of Square Roots of Polynomials and related problems
- Partial Derivatives in Arithmetic Complexity and beyond

> Publications > Approaching the chasm at depth four