An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields

Authors Mrinal Kumar, Ramprasad Saptharishi



PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.31.pdf
  • Filesize: 0.7 MB
  • 30 pages

Document Identifiers

Author Details

Mrinal Kumar
Ramprasad Saptharishi

Cite AsGet BibTex

Mrinal Kumar and Ramprasad Saptharishi. An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 31:1-31:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CCC.2017.31

Abstract

In this paper, we show exponential lower bounds for the class of homogeneous depth-5 circuits over all small finite fields. More formally, we show that there is an explicit family {P_d} of polynomials in VNP, where P_d is of degree d in n = d^{O(1)} variables, such that over all finite fields GF(q), any homogeneous depth-5 circuit which computes P_d must have size at least exp(Omega_q(sqrt{d})). To the best of our knowledge, this is the first super-polynomial lower bound for this class for any non-binary field. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et al., Fournier et al., Kayal et al., Kumar-Saraf] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski, Grigoriev-Razborov]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from GF(q)^n to GF(q) as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf [Kumar-Saraf].
Keywords
  • arithmetic circuits
  • lower bounds
  • separations
  • depth reduction

Metrics

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

References

  1. Manindra Agrawal, Eric Allender, and Samir Datta. On TC⁰, AC⁰, and Arithmetic Circuits. Journal of Computer and System Sciences, 60(2):395-421, 2000. URL: http://dx.doi.org/10.1006/jcss.1999.1675.
  2. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings of the \ifnumcomp2008<1966\nth\intcalcSub20081959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2008)\ifnumcomp2008<1975\nth\intcalcSub20081959 Annual Symposium on Switching and Automata Theory (SWAT 2008)\nth\intcalcSub20081959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 67-75, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.32.
  3. Suman K. Bera and Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication. In 30th Conference on Computational Complexity (CCC 2015), volume 33 of Leibniz International Proceedings in Informatics (LIPIcs), pages 183-197. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.183.
  4. Suryajith Chillara and Partha Mukhopadhyay. On the limits of depth reduction at depth 3 over small finite fields. In Mathematical Foundations of Computer Science (MFCS), pages 177-188, 2014. http://arxiv.org/abs/1401.0189, URL: http://dx.doi.org/10.1007/978-3-662-44465-8_16.
  5. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 128-135, 2014. URL: http://dx.doi.org/10.1145/2591796.2591824.
  6. Dima Grigoriev and Marek Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In Proceedings of the \nth\intcalcSub19981968 Annual ACM Symposium on Theory of Computing (STOC 1998), pages 577-582, 1998. URL: http://dx.doi.org/10.1145/276698.276872.
  7. 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. Preliminary version in the \ifnumcomp1998<1966\nth\intcalcSub19981959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1998)\ifnumcomp1998<1975\nth\intcalcSub19981959 Annual Symposium on Switching and Automata Theory (SWAT 1998)\nth\intcalcSub19981959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998). URL: http://dx.doi.org/10.1007/s002009900021.
  8. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic Circuits: A Chasm at Depth Three. In Proceedings of the \ifnumcomp2013<1966\nth\intcalcSub20131959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2013)\ifnumcomp2013<1975\nth\intcalcSub20131959 Annual Symposium on Switching and Automata Theory (SWAT 2013)\nth\intcalcSub20131959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 578-587, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.68.
  9. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. Journal of the ACM, 61(6):33:1-33:16, 2014. Preliminary version in the \ifnumcomp2013<1996\nth\intcalcSub20131985 Annual Structure in Complexity Theory Conference (Structures 2013)\ifnumcomp2013<2015\nth\intcalcSub20131985 Annual IEEE Conference on Computational Complexity (CCC 2013)\nth\intcalcSub20131985 Annual Computational Complexity Conference (CCC 2013). URL: http://dx.doi.org/10.1145/2629541.
  10. Laurent Hyafil. On the parallel evaluation of multivariate polynomials. SIAM Journal of Computing, 8(2):120-123, 1979. Preliminary version in the \nth\intcalcSub19781968 Annual ACM Symposium on Theory of Computing (STOC 1978). URL: http://dx.doi.org/10.1137/0208010.
  11. Kyriakos Kalorkoti. A Lower Bound for the Formula Size of Rational Functions. SIAM Journal of Computing, 14(3):678-687, 1985. URL: http://dx.doi.org/10.1137/0214050.
  12. Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. In Electronic Colloquium on Computational Complexity (ECCC) TR12-081, 2012. URL: https://eccc.weizmann.ac.il/report/2012/081/.
  13. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Circuits. In Proceedings of the \ifnumcomp2014<1966\nth\intcalcSub20141959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2014)\ifnumcomp2014<1975\nth\intcalcSub20141959 Annual Symposium on Switching and Automata Theory (SWAT 2014)\nth\intcalcSub20141959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.15.
  14. Neeraj Kayal and Chandan Saha. Lower bounds for depth three arithmetic circuits with small bottom fanin. In 30th Conference on Computational Complexity (CCC 2015), volume 33 of Leibniz International Proceedings in Informatics (LIPIcs), pages 158-208. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.158.
  15. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 146-153, 2014. URL: http://dx.doi.org/10.1145/2591796.2591847.
  16. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012. http://arxiv.org/abs/1006.4700, URL: http://dx.doi.org/10.1016/j.tcs.2012.03.041.
  17. Mrinal Kumar and Ramprasad Saptharishi. Finer Separations Between Shallow Arithmetic Circuits. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), volume 65 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.38.
  18. Mrinal Kumar and Shubhangi Saraf. The limits of depth reduction for arithmetic formulas: it’s all about the top fan-in. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 136-145, 2014. URL: http://dx.doi.org/10.1145/2591796.2591827.
  19. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In Proceedings of the \ifnumcomp2014<1966\nth\intcalcSub20141959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2014)\ifnumcomp2014<1975\nth\intcalcSub20141959 Annual Symposium on Switching and Automata Theory (SWAT 2014)\nth\intcalcSub20141959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.46.
  20. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. Available on http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.2644. URL: http://dx.doi.org/10.1007/BF01294256.
  21. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. In Proceedings of the \nth\intcalcSub20101968 Annual ACM Symposium on Theory of Computing (STOC 2010), pages 659-666, 2010. URL: http://dx.doi.org/10.1145/2535928.
  22. Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. URL: http://dx.doi.org/10.1007/BF01137685.
  23. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/.
  24. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the \nth\intcalcSub19871968 Annual ACM Symposium on Theory of Computing (STOC 1987), pages 77-82, 1987. URL: http://dx.doi.org/10.1145/28395.28404.
  25. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. Preliminary version in the \nth\intcalcSub20131975 Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 2013). URL: http://dx.doi.org/10.1016/j.ic.2014.09.004.
  26. Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM Journal of Computing, 12(4):641-644, 1983. Preliminary version in the \nth\intcalcSub19811975 Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 1981). URL: http://dx.doi.org/10.1137/0212043.
  27. Marc van Leeuwen. URL: https://math.stackexchange.com/questions/298836/sylvester-rank-inequality-operatornamerank-a-operatornamerankb-leq-o/298944#298944.
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