Lower Bounds for Arithmetic Circuits via the Hankel Matrix

Authors Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre



PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.24.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Nathanaël Fijalkow
  • CNRS, LaBRI, Bordeaux, France
  • The Alan Turing Institute of data science, London, United Kingdom
Guillaume Lagarde
  • LaBRI, Bordeaux, France
Pierre Ohlmann
  • Université de Paris, IRIF, CNRS, F-75013 Paris, France
Olivier Serre
  • Université de Paris, IRIF, CNRS, F-75013 Paris, France

Cite AsGet BibTex

Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, and Olivier Serre. Lower Bounds for Arithmetic Circuits via the Hankel Matrix. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.24

Abstract

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. To analyse circuits we count their number of parse trees, which describe the non-associative computations realised by the circuit. In the non-commutative setting a circuit computing a polynomial of degree d has at most 2^{O(d)} parse trees. Previous superpolynomial lower bounds were known for circuits with up to 2^{d^{1/3-ε}} parse trees, for any ε > 0. Our main result is to reduce the gap by showing a superpolynomial lower bound for circuits with just a small defect in the exponent for the total number of parse trees, that is 2^{d^{1 - ε}}, for any ε > 0. In the commutative setting a circuit computing a polynomial of degree d has at most 2^{O(d log d)} parse trees. We show a superpolynomial lower bound for circuits with up to 2^{d^{1/3 - ε}} parse trees, for any ε > 0. When d is polylogarithmic in n, we push this further to up to 2^{d^{1 - ε}} parse trees. While these two main results hold in the associative setting, our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish the polynomials (xy)z and x(yz). Our first and main conceptual result is a characterization result: we show that the size of the smallest circuit computing a given non-associative polynomial is exactly the rank of a matrix constructed from the polynomial and called the Hankel matrix. This result applies to the class of all circuits in both commutative and non-commutative settings, and can be seen as an extension of the seminal result of Nisan giving a similar characterization for non-commutative algebraic branching programs. Our key technical contribution is to provide generic lower bound theorems based on analyzing and decomposing the Hankel matrix, from which we derive the results mentioned above. The study of the Hankel matrix also provides a unifying approach for proving lower bounds for polynomials in the (classical) associative setting. We demonstrate this by giving alternative proofs of recent lower bounds as corollaries of our generic lower bound results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Algebraic complexity theory
Keywords
  • Arithmetic Circuit Complexity
  • Lower Bounds
  • Parse Trees
  • Hankel Matrix

Metrics

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

References

  1. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669-697, 2015. Google Scholar
  2. Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay. Non-commutative arithmetic circuits: Depth reduction and size lower bounds. Theoretical Computer Science, 209(1-2):47-86, 1998. Google Scholar
  3. Vikraman Arvind and S. Raja. Some lower bound results for set-multilinear arithmetic computations. Chicago Journal of Theoretical Computer Science, 2016, 2016. Google Scholar
  4. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22:317-330, 1983. Google Scholar
  5. Symeon Bozapalidis and Olympia Louscou-Bozapalidou. The rank of a formal tree power series. Theoretical Computer Science, 27:211-215, 1983. Google Scholar
  6. Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness amplification for non-commutative arithmetic circuits. In Proceedings of the 33rd Computational Complexity Conference (CCC 2018), volume 102 of LIPIcs, pages 12:1-12:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  7. Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff. Separating multilinear branching programs and formulas. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC 2012), pages 615-624. ACM, 2012. Google Scholar
  8. Nathanaël Fijalkow, Guillaume Lagarde, and Pierre Ohlmann. Tight bounds using hankel matrix for arithmetic circuits with unique parse trees. Electronic Colloquium on Computational Complexity (ECCC), 25:38, 2018. URL: https://eccc.weizmann.ac.il/report/2018/038.
  9. Michel Fliess. Matrices de Hankel. Journal de Mathématiques Pures et Appliquées, 53:197-222, 1974. Google Scholar
  10. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the 46th Symposium on Theory of Computing, (STOC 2014), pages 867-875. ACM, 2014. Google Scholar
  11. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Computational Complexity, 26(4):835-880, 2017. Google Scholar
  12. Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff. Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society, 24(3):871-898, 2011. Google Scholar
  13. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pages 355-364. ACM, 2003. Google Scholar
  14. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In Proceedings of the 46th Symposium on Theory of Computing, (STOC 2014), pages 146-153. ACM, 2014. Google Scholar
  15. Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees. Computational Complexity, pages 1-72, 2018. https://doi.org/10.1007/s00037-018-0171-9. Google Scholar
  16. Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 23:94, 2016. Google Scholar
  17. Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for non-commutative skew circuits. Theory of Computing, 12(1):1-38, 2016. Google Scholar
  18. Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. Journal of Complexity, 24(1):16-38, 2008. Google Scholar
  19. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd Symposium on Theory of Computing (STOC 1991), pages 410-418. ACM, 1991. Google Scholar
  20. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  21. C. Ramya and B. V. Raghavendra Rao. Lower bounds for special cases of syntactic multilinear abps. In Proceedings of the 24th International Computing and Combinatorics Conference (COCOON 2018), volume 10976 of Lecture Notes in Computer Science, pages 701-712. Springer, 2018. Google Scholar
  22. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. Google Scholar
  23. Ramprasad Saptharishi and Anamay Tengse. Quasi-polynomial hitting sets for circuits with restricted parse trees. Electronic Colloquium on Computational Complexity (ECCC), 24:135, 2017. Google Scholar
  24. Seinosuke Toda. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. Systems, E75-D(1):116-124, 1992. Google Scholar
  25. Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189-201, 1979. 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