Document Open Access Logo

Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Authors Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.21.pdf
  • Filesize: 0.61 MB
  • 24 pages

Document Identifiers

Author Details

Markus Bläser
  • Department of Computer Science, Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Christian Ikenmeyer
  • University of Liverpool, UK
Meena Mahajan
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Anurag Pandey
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Nitin Saurabh
  • Technion-IIT, Haifa, Israel

Funding

  • Ikenmeyer, Christian: Part of this research was done when CI was at the Max Planck Institute for Software Systems, Saarbrücken, Germany. CI was supported by DFG grant IK 116/2-1.
  • Pandey, Anurag: Supported by the Chair of Raimund Seidel, Department of Computer Science, Saarland University, Saarbrücken, Germany.
  • Saurabh, Nitin: Part of this work was done when the author was at the Max Planck Institute for Informatics, Saarbrücken, Germany.

Acknowledgements

We thank Michael Forbes for illuminating discussions and for telling us about his (correct) intuition concerning Nisan’s result. We thank the Simons Institute for the Theory of Computing (Berkeley), Schloss Dagstuhl - Leibniz-Zentrum für Informatik (Dagstuhl), and the International Centre for Theoretical Sciences (Bengaluru), for hosting us during several phases of this research.

Cite AsGet BibTex

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic Branching Programs, Border Complexity, and Tangent Spaces. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.21

Abstract

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Complexity classes
Keywords
  • Algebraic Branching Programs
  • Border Complexity
  • Tangent Spaces
  • Lower Bounds
  • Geometric Complexity Theory
  • Flows
  • VQP
  • VNP

Metrics

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

References

  1. Eric Allender and Fengming Wang. On the power of algebraic branching programs of width two. Comput. Complex., 25(1):217-253, March 2016. URL: https://doi.org/10.1007/s00037-015-0114-7.
  2. Jarod Alper, Tristram Bogart, and Mauricio Velasco. A lower bound for the determinantal complexity of a hypersurface. Foundations of Computational Mathematics, pages 1-8, 2015. Google Scholar
  3. Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity testing and lower bounds for read-k oblivious algebraic branching programs. In Proceedings of the 31st Conference on Computational Complexity, CCC ’16, Dagstuhl, DEU, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  4. Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. Comput., 21(1):54-58, 1992. URL: https://doi.org/10.1137/0221006.
  5. D. Bini. Relations between exact and approximate bilinear algorithms. applications. CALCOLO, 17(1):87-97, January 1980. URL: https://doi.org/10.1007/BF02575865.
  6. Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti. O(n^2.7799) complexity for n × n approximate matrix multiplication. Inf. Process. Lett., 8(5):234-235, 1979. URL: https://doi.org/10.1016/0020-0190(79)90113-3.
  7. Markus Bläser and Christian Ikenmeyer. Introduction to geometric complexity theory, 2018. , version from July 25. URL: http://pcwww.liv.ac.uk/~iken/teaching_sb/summer17/introtogct/gct.pdf.
  8. J.A. Bondy and U.S.R Murty. Graph Theory. Springer Publishing Company, Incorporated, 2008. Google Scholar
  9. Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On algebraic branching programs of small width. J. ACM, 65(5), August 2018. URL: https://doi.org/10.1145/3209663.
  10. Peter Bürgisser. Erratum to the complexity of factors of multivariate polynomials. URL: https://www.math.tu-berlin.de/fileadmin/i26_fg-buergisser/erratum_factors.pdf.
  11. Peter Bürgisser. Completeness and Reduction in Algebraic Complexity Theory. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000. Google Scholar
  12. Peter Bürgisser. The complexity of factors of multivariate polynomials. Found. Comput. Math., 4(4):369-396, 2004. URL: https://doi.org/10.1007/s10208-002-0059-5.
  13. Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi. Algebraic complexity theory, volume 315. Springer Science &Business Media, 2013. Google Scholar
  14. Peter Bürgisser, J.M. Landsberg, Laurent Manivel, and Jerzy Weyman. An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP. SIAM J. Comput., 40(4):1179-1209, 2011. Google Scholar
  15. Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A quadratic lower bound for algebraic branching programs. CoRR, abs/1911.11793, 2019. To appear in the proceedings of Conference on Computational Complexity, CCC'20. URL: http://arxiv.org/abs/1911.11793.
  16. Michael Forbes. Some concrete questions on the Border Complexity of polynomials, 2016. Talk at the Workshop on Algebraic Complexity Theory (WACT) 2016 in Tel Aviv. URL: https://www.youtube.com/watch?v=1HMogQIHT6Q.
  17. Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas. Nonnegative rank measures and monotone algebraic branching programs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 150 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 15, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. Google Scholar
  18. Fulvio Gesmundo. Geometric aspects of iterated matrix multiplication. Journal of Algebra, 461:42-64, 2016. Google Scholar
  19. Fulvio Gesmundo, Christian Ikenmeyer, and Greta Panova. Geometric complexity theory and matrix powering. Differential Geom. Appl., 55:106-127, 2017. URL: https://doi.org/10.1016/j.difgeo.2017.07.001.
  20. Bruno Grenet. An upper bound for the permanent versus determinant problem, 2011. Manuscript. URL: http://www.lirmm.fr/~grenet/publis/Gre11.pdf.
  21. Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming, volume 55 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 34, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016. Google Scholar
  22. Joos Heintz and Malte Sieveking. Lower bounds for polynomials with algebraic coefficients. Theoretical Computer Science, 11(3):321-330, 1980. Google Scholar
  23. Jesko Hüttenhain. Geometric Complexity Theory and Orbit Closures of Homogeneous Forms. PhD thesis, Technische Universität Berlin, July 2017. Google Scholar
  24. Jesko Hüttenhain and Pierre Lairez. The boundary of the orbit of the 3-by-3 determinant polynomial. Comptes Rendus Mathematique, 354(9):931-935, 2016. Google Scholar
  25. Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of full rank algebraic branching programs. ACM Trans. Comput. Theory, 11(1), November 2018. URL: https://doi.org/10.1145/3282427.
  26. Mrinal Kumar. On top fan-in vs formal degree for depth-3 arithmetic circuits, 2018. URL: https://eccc.weizmann.ac.il/report/2018/068/.
  27. Mrinal Kumar. A quadratic lower bound for homogeneous algebraic branching programs. computational complexity, 28(3):409-435, 2019. URL: https://doi.org/10.1007/s00037-019-00186-3.
  28. J. M. Landsberg. Geometric complexity theory: an introduction for geometers. ANNALI DELL'UNIVERSITA' DI FERRARA, 61(1):65-117, May 2015. Google Scholar
  29. J. M. Landsberg. Geometry and Complexity Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108183192.
  30. Meena Mahajan and V. Vinay. Determinant: combinatorics, algorithms, and complexity. Chicago J. Theoret. Comput. Sci., pages Article 5, 26 pp. (electronic), 1997. Google Scholar
  31. Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. Journal of Complexity, 24(1):16-38, 2008. Google Scholar
  32. K.D. Mulmuley and M. Sohoni. Geometric Complexity Theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496-526 (electronic), 2001. Google Scholar
  33. K.D. Mulmuley and M. Sohoni. Geometric Complexity Theory. II. Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175-1206, 2008. Google Scholar
  34. D. Mumford. Algebraic geometry. I: Complex projective varieties. Classics in mathematics. Springer-Verlag, Berlin, 1995. Reprint of the 1976 edition in Grundlehren der mathematischen Wissenschaften, vol. 221. Google Scholar
  35. Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410-418. ACM, 1991. Google Scholar
  36. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):Art. 40, 15, 2013. URL: https://doi.org/10.1145/2535928.
  37. Claus-Peter Schnorr. Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials. In International Symposium on Mathematical Foundations of Computer Science, pages 135-147. Springer, 1977. Google Scholar
  38. Srikanth Srinivasan. Strongly exponential separation between monotone VP and monotone VNP, 2019. URL: http://arxiv.org/abs/1903.01630.
  39. Volker Strassen. Polynomials with rational coefficients which are hard to compute. SIAM Journal on Computing, 3(2):128-149, 1974. Google Scholar
  40. Seinosuke Toda. Classes of Arithmetic Circuits Capturing the Complexity of the Determinant. IEICE TRANS. INF. &SYST., E75-D(1):116-124, 1992. Google Scholar
  41. L. G. Valiant. Completeness classes in algebra. In Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979), pages 249-261. ACM, New York, 1979. Google Scholar
  42. Amir Yehudayoff. Separating monotone VP and VNP. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 425–429, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316311.
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