Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

Shpilka & Wigderson (IEEE conference on computational complexity, vol 87, 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 at most \({\tau}\) computing an explicit \({N}\)-variate polynomial of degree \({d}\) over \({{\mathbb{F}}}\). Meanwhile, Nisan & Wigderson (Comp Complex 6(3):217–234, 1997) had posed the problem of proving super-polynomial 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^{\mu}}\), for any fixed \({\mu < 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}\)).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Manindra Agrawal & V. Vinay (2008). Arithmetic Circuits: A Chasm at Depth Four. In 49th Annual IEEE Symposium on Foundations of Computer Science, 67–75.

  • Alon Noga (2009) Perturbed Identity Matrices Have High Rank: Proof and Applications. Combinatorics, Probability & Computing 18(1–2): 3–15

    Article  MathSciNet  MATH  Google Scholar 

  • Suman K. Bera & Amit Chakrabarti (2015). A Depth-Five Lower Bound for Iterated Matrix Multiplication. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, 183–197.

  • Paul Erdös (1930-1932). Beweis eines Satzes von Tschebyschef. Acta Sci. Math. (Szeged) 5, 194–198.

  • Hervé Fournier, Nutan Limaye, Guillaume Malod & Srikanth Srinivasan (2014). Lower bounds for depth 4 formulas computing iterated matrix multiplication. In 46th ACM Symposium on Theory of Computing (STOC 2014), 128–135.

  • Dima Grigoriev & Marek Karpinski (1998). An Exponential Lower Bound for Depth 3 Arithmetic Circuits. In 30th ACM Symposium on Theory of Computing, 577–582. URL http://doi.acm.org/10.1145/276698.276872.

  • Grigoriev Dima, Razborov Alexander A. (2000) Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. Appl. Algebra Eng. Commun. Comput. 10(6): 465–487

    Article  MathSciNet  MATH  Google Scholar 

  • Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2013a). Arithmetic Circuits: A Chasm at Depth Three. In IEEE Symposium on Foundations of Computer Science, 578–587.

  • Ankit Gupta, Neeraj Kayal, Pritish Kamath & Ramprasad Saptharishi (2013b). Approaching the chasm at depth four. In 2013 IEEE Conference on Computational Complexity, 65–73.

  • Hardy G. H., Ramanujan S. (1918) Asymptotic formulae in Combinatory Analysis. Proceedings of the London Mathematical Society s2-17(1): 75–115

    Article  MathSciNet  MATH  Google Scholar 

  • Kayal Neeraj (2012) An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity 19: 81

    Google Scholar 

  • Neeraj Kayal, Nutan Limaye, Chandan Saha & Srikanth Srinivasan (2014a). An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. In 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, USA, October 18–21, 2014, 61–70.

  • Neeraj Kayal, Nutan Limaye, Chandan Saha & Srikanth Srinivasan (2014b). Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In 46th ACM Symposium on Theory of Computing (STOC 2014), 119–127.

  • Neeraj Kayal & Chandan Saha (2015). Lower Bounds for Sums of Products of Low arity Polynomials. Electronic Colloquium on Computational Complexity 22, 73. URL http://eccc.hpi-web.de/report/2015/073.

  • Neeraj Kayal, Chandan Saha & Ramprasad Saptharishi (2014c). A super-polynomial lower bound for regular arithmetic formulas. In 46th ACM Symposium on Theory of Computing (STOC 2014), 146–153.

  • Koiran Pascal (2012) Arithmetic Circuits: The Chasm at Depth Four Gets Wider. Theoretical Computer Science 448: 56–65

    Article  MathSciNet  MATH  Google Scholar 

  • Mrinal Kumar & Shubhangi Saraf (2014a). On the Power of Homogeneous Depth 4 Arithmetic Circuits. In 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, USA, October 18–21, 2014, 364–373.

  • Mrinal Kumar & Shubhangi Saraf (2014b). Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits. In International Colloquium on Automata, Languages and Programming (1), 751–762.

  • Mrinal Kumar & Shubhangi Saraf (2015). Sums of products of polynomials in few variables : lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity 22, 71. URL http://eccc.hpi-web.de/report/2015/071.

  • D.E. Littlewood (1950). The Theory of Group Characters and Matrix Representations of Groups. Ams Chelsea Publishing. AMS Chelsea Pub., 2nd edition.

  • Noam Nisan & Avi Wigderson (1997). Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity 6(3), 217–234. Available at http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NW96/final.pdf.

  • Raz Ran, Yehudayoff Amir (2009) Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity 18(2): 171–207

    Article  MathSciNet  MATH  Google Scholar 

  • H. J. Ryser (1963). Combinatorial Mathematics. Math. Assoc. of America 14.

  • Ramprasad Saptharishi (2014). Personal Communication.

  • Amir Shpilka (2001). Lower Bounds for Small Depth Arithmetic and Boolean Circuits. Ph.D. thesis, The Hebrew University.

  • Amir Shpilka & Avi Wigderson (1999). Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. In IEEE Conference on Computational Complexity, 87–. Available at http://eccc.hpi-web.de/report/1999/023/.

  • Shpilka Amir, Wigderson Avi (2001) Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1): 1–27

    Article  MathSciNet  MATH  Google Scholar 

  • Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 207–388. ISSN 1551-305X. URL http://dx.doi.org/10.1561/0400000039.

  • Sébastien Tavenas (2013). Improved Bounds for Reduction to Depth 4 and Depth 3. In International Symposium on Mathematical Foundations of Computer Science, 813–824.

Download references

Author information

Authors and Affiliations

  1. Microsoft Research India, Bengaluru, India

    Neeraj Kayal

  2. Indian Institute of Science, Bengaluru, India

    Chandan Saha

Authors
  1. Neeraj Kayal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chandan Saha
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Neeraj Kayal.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kayal, N., Saha, C. Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin. comput. complex. 25, 419–454 (2016). https://doi.org/10.1007/s00037-016-0132-0

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00037-016-0132-0

Keywords

Subject classification

Search

Navigation