Document Open Access Logo

Degree-Restricted Strength Decompositions and Algebraic Branching Programs

Authors Fulvio Gesmundo , Purnata Ghosal, Christian Ikenmeyer, Vladimir Lysikov

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.20.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Fulvio Gesmundo
  • Saarland University, Saarbrücken, Germany
Purnata Ghosal
  • University of Warwick, UK
Christian Ikenmeyer
  • University of Warwick, UK
Vladimir Lysikov
  • QMATH, Department of Mathematical Sciences, University of Copenhagen, Denmark

Funding

  • Ghosal, Purnata: DFG IK 116/2-1 and EPSRC EP/W014882/1. The work was done while this author was at the University of Liverpool.
  • Ikenmeyer, Christian: DFG IK 116/2-1 and EPSRC EP/W014882/1. The work was done while this author was at the University of Liverpool.
  • Lysikov, Vladimir: ERC 818761 and VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059).

Acknowledgements

We would like to thank Daniele Agostini for many helpful discussions during the development of this work. We also thank Edoardo Ballico, Luca Chiantini, Giorgio Ottaviani and Kristian Ranestad for pointing out useful references on the Noether-Lefschetz property and related results. We thank the anonymous referees for their helpful comments.

Cite AsGet BibTex

Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov. Degree-Restricted Strength Decompositions and Algebraic Branching Programs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.20

Abstract

We analyze Kumar’s recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that gives better bounds in some cases. The lower bound relies on Noether-Lefschetz type conditions on the hypersurface defined by the homogeneous polynomial. In the explicit example that we provide, the lower bound is proved resorting to classical intersection theory. Furthermore, we use similar methods to improve the known lower bound methods for slice rank of polynomials. We consider a sequence of polynomials that have been studied before by Shioda and show that for these polynomials the improved lower bound matches the known upper bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Lower bounds
  • Slice rank
  • Strength of polynomials
  • Algebraic branching programs

Metrics

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

References

  1. T. Ananyan and M. Hochster. Small subalgebras of polynomial rings and Stillman’s conjecture. J. Amer. Math. Soc., 33(1):291-309, 2020. Google Scholar
  2. M. F. Atiyah and I. G. Macdonald. Introduction to Commutative Algebra. Addison Wesley, 1969. Google Scholar
  3. E. Ballico, A. Bik, A. Oneto, and E. Ventura. The set of forms with bounded strength is not closed. arXiv, 2020. URL: http://arxiv.org/abs/2012.01237.
  4. E. Ballico, A. Bik, A. Oneto, and E. Ventura. Strength and slice rank of forms are generically equal, 2021. URL: http://arxiv.org/abs/2102.11549.
  5. A. Bik. Strength and noetherianity for infinite tensors. PhD thesis, Universität Bern, 2020. Google Scholar
  6. P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin, 1997. Google Scholar
  7. P. Bürgisser, F. Cucker, and P. Lairez. Rigid continuation paths II. Structured polynomial systems. arXiv, 2020. URL: http://arxiv.org/abs/2010.10997.
  8. P. Bürgisser, C. Ikenmeyer, and G. Panova. No occurrence obstructions in geometric complexity theory. J. Amer. Math. Soc., 32(1):163-193, 2019. Google Scholar
  9. E. Carlini, L. Chiantini, and A. V. Geramita. Complete intersections on general hypersurfaces. Michigan Math. J., 57:121-136, 2008. Google Scholar
  10. P. Chatterjee, M. Kumar, A. She, and B. L. Volk. A Quadratic Lower Bound for Algebraic Branching Programs. In 35th Computational Complexity Conference (CCC 2020), volume 169 of LIPIcs, pages 2:1-2:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  11. H. Davenport and D. J. Lewis. Non-homogeneous cubic equations. J. London Math. Soc., 39:657-671, 1964. Google Scholar
  12. Jan Draisma. Topological Noetherianity of polynomial functors. Journal of the American Mathematical Society, 32(3):691-707, 2019. Google Scholar
  13. D. Eisenbud. Commutative Algebra: with a view toward algebraic geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. Google Scholar
  14. D. Eisenbud and J. Harris. 3264 and All That - A Second Course in Algebraic Geometry. Cambridge University Press, Cambridge, 2016. Google Scholar
  15. W. Fulton. Intersection theory, volume 2 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer-Verlag, Berlin, second edition, 1998. Google Scholar
  16. P. Griffiths and J. Harris. On the Noether-Lefschetz theorem and some remarks on codimension-two cycles. Math. Ann., 271(1):31-51, 1985. Google Scholar
  17. J. Harris. Algebraic geometry. A first course, volume 133 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1992. Google Scholar
  18. C. Ikenmeyer and G. Panova. Rectangular Kronecker coefficients and plethysms in geometric complexity theory. Adv. Math., 319:40-66, 2017. Google Scholar
  19. M. Kumar. A quadratic lower bound for homogeneous algebraic branching programs. Comput. Complex., 28(3):409-435, 2019. Google Scholar
  20. M. Kumar and B. L. Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 4:1-4:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  21. N. Nisan. Lower bounds for non-commutative computation. In Proceedings of the 23rd ACM Symp. on Th. of Comp., STOC'91, pages 410-418, New York, NY, USA, 1991. ACM. Google Scholar
  22. W. F. Sawin and T. Tao. Notes on the "slice rank" of tensors, 2016. available at URL: https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/.
  23. W. M. Schmidt. The density of integer points on homogeneous varieties. Acta Math., 154(3-4):243-296, 1985. Google Scholar
  24. T. Shioda. On the Picard number of a complex projective variety. Ann. Sci. École Norm. Sup. (4), 14(3):303-321, 1981. Google Scholar
  25. T. Shioda. Algebraic cycles on a certain hypersurface. In Algebraic geometry (Tokyo/Kyoto, 1982), volume 1016 of Lecture Notes in Math., pages 271-294. Springer, Berlin, 1983. Google Scholar
  26. Leslie G. Valiant. Completeness Classes in Algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249-261. ACM, 1979. Google Scholar
  27. X. Wu. On a conjecture of Griffiths-Harris generalizing the Noether-Lefschetz theorem. Duke Math. J., 60(2):465-472, 1990. 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