Document Open Access Logo

Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin

Authors Neeraj Kayal, Chandan Saha

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.158.pdf
  • Filesize: 0.7 MB
  • 25 pages

Document Identifiers

Author Details

Neeraj Kayal
Chandan Saha

Cite AsGet BibTex

Neeraj Kayal and Chandan Saha. Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 158-182, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CCC.2015.158

Abstract

Shpilka and Wigderson (CCC 99) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field F of characteristic zero. We resolve this problem by proving a N^(Omega(d/t)) lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin at most t computing an explicit N-variate polynomial of degree d over F. Meanwhile, Nisan and Wigderson (CC 97) had posed the problem of proving superpolynomial 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^(u), for any fixed u < 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).
Keywords
  • arithmetic circuits
  • depth three circuits
  • lower bound
  • bottom fanin

Metrics

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

References

  1. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In FOCS, pages 67-75, 2008. Google Scholar
  2. Noga Alon. Perturbed Identity Matrices Have High Rank: Proof and Applications. Combinatorics, Probability & Computing, 18(1-2):3-15, 2009. Google Scholar
  3. Paul Erdös. Beweis eines Satzes von Tschebyschef. Acta Sci. Math. (Szeged), 5:194-198, 1930-1932. Google Scholar
  4. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In STOC, pages 128-135, 2014. 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 lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput., 10(6):465-487, 2000. Google Scholar
  7. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. In FOCS, pages 578-587, 2013. Google Scholar
  8. Ankit Gupta, Neeraj Kayal, Pritish Kamath, and Ramprasad Saptharishi. Approaching the chasm at depth four. In CCC, 2013. Google Scholar
  9. G. H. Hardy and S. Ramanujan. Asymptotic formulae in combinatory analysis. Proceedings of the London Mathematical Society, s2-17(1):75-115, 1918. Google Scholar
  10. 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
  11. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. In FOCS, pages 61-70, 2014. Google Scholar
  12. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In STOC, pages 119-127, 2014. Google Scholar
  13. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In STOC, pages 146-153, 2014. Google Scholar
  14. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012. Google Scholar
  15. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In FOCS, pages 364-373, 2014. Google Scholar
  16. Mrinal Kumar and Shubhangi Saraf. Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. In ICALP (1), pages 751-762, 2014. Google Scholar
  17. D.E. Littlewood. The Theory of Group Characters and Matrix Representations of Groups. Ams Chelsea Publishing. AMS Chelsea Pub., 2nd edition, 1950. Google Scholar
  18. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. Available at URL: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NW96/final.pdf.
  19. H. J. Ryser. Combinatorial mathematics. Math. Assoc. of America, 14, 1963. Google Scholar
  20. Ramprasad Saptharishi. Personal communication, 2014. Google Scholar
  21. Amir Shpilka. Lower Bounds for Small Depth Arithmetic and Boolean Circuits. PhD thesis, The Hebrew University, 2001. Google Scholar
  22. Amir Shpilka and Avi Wigderson. Depth-3 arithmetic formulae over fields of characteristic zero. In IEEE Conference on Computational Complexity, pages 87-, 1999. Available at URL: http://eccc.hpi-web.de/report/1999/023/.
  23. Amir Shpilka and Avi Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10(1):1-27, 2001. Google Scholar
  24. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5:207-388, March 2010. Google Scholar
  25. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. In MFCS, pages 813-824, 2013. 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