Document Open Access Logo

Multi-k-ic Depth Three Circuit Lower Bound

Authors Neeraj Kayal, Chandan Saha

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.527.pdf
  • Filesize: 0.66 MB
  • 13 pages

Document Identifiers

Author Details

Neeraj Kayal
Chandan Saha

Cite AsGet BibTex

Neeraj Kayal and Chandan Saha. Multi-k-ic Depth Three Circuit Lower Bound. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 527-539, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.527

Abstract

In a multi-k-ic depth three circuit every variable appears in at most k of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables (as the formal degree of a multi-k-ic depth three circuit can be kn where n is the number of variables). The problem of proving lower bounds for depth three circuits with high formal degree has gained in importance following a work by Gupta, Kamath, Kayal and Saptharishi [7] on depth reduction to high formal degree depth three circuits. In this work, we show an exponential lower bound for multi-k-ic depth three circuits for any arbitrary constant k.
Keywords
  • arithmetic circuits
  • multilinear circuits
  • depth three circuits
  • lower bound
  • individual degree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. Jacobian hits circuits: hitting-sets, lower bounds for depth-d occur-k formulas & depth-3 transcendence degree-k circuits. In STOC, pages 599-614, 2012. Google Scholar
  2. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In FOCS, pages 67-75, 2008. Google Scholar
  3. Michael A. Forbes and Amir Shpilka. Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 243-252, 2013. Google Scholar
  4. Bruno Grenet, Pascal Koiran, Natacha Portier, and Yann Strozecki. The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent. In Proceedings of the 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 127-139, 2011. Google Scholar
  5. Dima Grigoriev and Marek Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In STOC, pages 577-582, 1998. Google Scholar
  6. Dima Grigoriev and Alexander A. Razborov. Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. In FOCS, pages 269-278, 1998. Google Scholar
  7. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. In Foundations of Computer Science (FOCS), pages 578-587, 2013. Google Scholar
  8. Ankit Gupta, Neeraj Kayal, Pritish Kamath, and Ramprasad Saptharishi. Approaching the chasm at depth four. In Conference on Computational Complexity (CCC), 2013. Google Scholar
  9. Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Technical report, Electronic Colloquium on Computational Complexity (ECCC), 2012. Google Scholar
  10. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. In Foundations of Computer Science (FOCS), pages 61-70, 2014. Google Scholar
  11. Neeraj Kayal and Chandan Saha. Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin. Electronic Colloquium on Computational Complexity (ECCC), 21:89, 2014. Google Scholar
  12. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In STOC, pages 146-153, 2014. Google Scholar
  13. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci., 448:56-65, 2012. Google Scholar
  14. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In Foundations of Computer Science (FOCS), pages 363-373, 2014. Google Scholar
  15. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. Google Scholar
  16. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2), 2009. Google Scholar
  17. Ran Raz. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6(1):135-177, 2010. Google Scholar
  18. Ran Raz and Amir Yehudayoff. Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity, 18(2):171-207, 2009. Google Scholar
  19. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. In MFCS, pages 813-824, 2013. Google Scholar
  20. L.\hspace0.04cmG. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing, 12(4):641-644, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact