Document Open Access Logo

Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings

Authors Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, Avi Wigderson

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2020.12.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • generators for invariant rings
  • succinct encodings

Metrics

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

Abstract

We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized such encodings for invariant rings of SL_n(ℂ)-representations. We provide simple examples that disprove this conjecture (under standard complexity assumptions).
We develop a general framework, denoted algebraic circuit search problems, that captures many important problems in algebraic complexity and computational invariant theory. This framework encompasses various proof systems in proof complexity and some of the central problems in invariant theory as exposed by the Geometric Complexity Theory (GCT) program, including the aforementioned problem of computing succinct encodings for generators for invariant rings.

Cite As Get BibTex

Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson. Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.12

Author Details

Ankit Garg
  • Microsoft Research, Bangalore, India
Christian Ikenmeyer
  • University of Liverpool, UK
Visu Makam
  • Institute for Advanced Study, Princeton, NJ, USA
Rafael Oliveira
  • University of Waterloo, Canada
Michael Walter
  • Korteweg-de Vries Institute for Mathematics, Institute for Theoretical Physics, Institute for Logic, Language &Computation, University of Amsterdam, The Netherlands
Avi Wigderson
  • Institute for Advanced Study, Princeton, NJ, US

Funding

  • Ikenmeyer, Christian: DFG grant IK 116/2-1.
  • Makam, Visu: NSF grant No. DMS -1638352 and NSF grant No. CCF-1412958.
  • Walter, Michael: NWO Veni grant 680-47-459.
  • Wigderson, Avi: NSF grant No. CCF-1412958 and NSF grant CCF-1900460.

References

  1. Manindra Agrawal and Somenath Biswas. Primality and identity testing via chinese remaindering. Journal of the ACM (JACM), 50(4):429-443, 2003. Google Scholar
  2. Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. STOC, 2018. Google Scholar
  3. Alexander I. Barvinok. New algorithms for linear k-matroid intersection and matroid k-parity problems. Mathematical Programming, 69(1):449-470, 1995. Google Scholar
  4. Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Generalized matrix completion and algebraic natural proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1193-1206, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188832.
  5. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: Geodesic 1st and 2nd order methods for moment maps and polytopes. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 845-861. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00055.
  6. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 883-897. IEEE, 2018. Google Scholar
  7. Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. Proceedings of Innovations in Theoretical Computer Science (ITCS 2018), 2017. URL: http://arxiv.org/abs/1711.08039.
  8. Peter Bürgisser and Christian Ikenmeyer. Fundamental invariants of orbit closures. J. Algebra, 477:390-434, 2017. URL: https://doi.org/10.1016/j.jalgebra.2016.12.035.
  9. Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. J. Amer. Math. Soc., 32(1):163-193, 2019. URL: https://doi.org/10.1090/jams/908.
  10. Harm Derksen and Gregor Kemper. Computational invariant theory, volume 130 of Encyclopaedia of Mathematical Sciences. Springer, Heidelberg, enlarged edition, 2015. With two appendices by Vladimir L. Popov, and an addendum by Norbert A'Campo and Popov, Invariant Theory and Algebraic Transformation Groups, VIII. URL: https://doi.org/10.1007/978-3-662-48422-7.
  11. Harm Derksen and Visu Makam. Generating invariant rings of quivers in arbitrary characteristic. J. Algebra, 489:435-445, 2017. URL: https://doi.org/10.1016/j.jalgebra.2017.06.035.
  12. Harm Derksen and Visu Makam. Polynomial degree bounds for matrix semi-invariants. Adv. Math., 310:44-63, 2017. URL: https://doi.org/10.1016/j.aim.2017.01.018.
  13. Harm Derksen and Visu Makam. Algorithms for orbit closure separation for invariants and semi-invariants of matrices. arXiv e-prints, January 2018. URL: http://arxiv.org/abs/1801.02043.
  14. Harm Derksen and Visu Makam. An exponential lower bound for the degrees of invariants of cubic forms and tensor actions. Advances in Mathematics, 368:107136, 2020. URL: https://doi.org/10.1016/j.aim.2020.107136.
  15. Harm Derksen and Jerzy Weyman. Semi-invariants of quivers and saturation for littlewood-richardson coefficients. Journal of the American Mathematical Society, 13(3):467-479, 2000. Google Scholar
  16. Mátyás Domokos and Alexander N Zubkov. Semi-invariants of quivers as determinants. Transformation groups, 6(1):9-24, 2001. Google Scholar
  17. Michael A. Forbes and Amir Shpilka. Explicit Noether normalization for simultaneous conjugation via polynomial identity testing. In Approximation, randomization, and combinatorial optimization, volume 8096 of Lecture Notes in Comput. Sci., pages 527-542. Springer, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_37.
  18. William Fulton and Joe Harris. Representation theory, volume 129 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991. A first course, Readings in Mathematics. URL: https://doi.org/10.1007/978-1-4612-0979-9.
  19. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. In 57th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2016, pages 109-117. IEEE Computer Soc., Los Alamitos, CA, 2016. Google Scholar
  20. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of brascamp-lieb inequalities, via operator scaling. Geometric and Functional Analysis, 28(1):100-145, 2018. Google Scholar
  21. Ankit Garg, Visu Makam, Rafael Oliveira, and Avi Wigderson. Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. arXiv e-prints, October 2019. URL: http://arxiv.org/abs/1910.01251v1.
  22. Joshua A Grochow and Toniann Pitassi. Circuit complexity, proof complexity, and polynomial identity testing. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 110-119. IEEE, 2014. Google Scholar
  23. Joshua A. Grochow and Youming Qiao. Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions. CoRR, abs/1907.00309, 2019. URL: http://arxiv.org/abs/1907.00309.
  24. David Hilbert. Ueber die Theorie der algebraischen Formen. Math. Ann., 36(4):473-534, 1890. URL: https://doi.org/10.1007/BF01208503.
  25. David Hilbert. Ueber die vollen Invariantensysteme. Math. Ann., 42(3):313-373, 1893. URL: https://doi.org/10.1007/BF01444162.
  26. Christian Ikenmeyer. Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients. PhD thesis, Institute of Mathematics, University of Paderborn, 2012. Online available at URL: http://digital.ub.uni-paderborn.de/ubpb/urn/urn:nbn:de:hbz:466:2-10472.
  27. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time. Comput. Complexity, 27(4):561-593, 2018. URL: https://doi.org/10.1007/s00037-018-0165-7.
  28. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  29. Jan Krajíček. Proof complexity, volume 170. Cambridge University Press, 2019. Google Scholar
  30. Visu Makam and Avi Wigderson. Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). arXiv e-prints, September 2019. URL: http://arxiv.org/abs/1909.00857.
  31. Ketan D. Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society, 30(1):225-309, 2017. URL: https://doi.org/10.1090/jams/864.
  32. Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496-526, 2001. URL: https://doi.org/10.1137/S009753970038715X.
  33. Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175-1206, 2008. URL: https://doi.org/10.1137/080718115.
  34. David Mumford. Geometric invariant theory. Ergebnisse der Mathematik und ihrer Grenzgebiete, Neue Folge, Band 34. Springer-Verlag, Berlin-New York, 1965. Google Scholar
  35. Aidan Schofield and Michel Van den Bergh. Semi-invariants of quivers for arbitrary dimension vectors. Indagationes Mathematicae, 12(1):125-138, 2001. Google Scholar
  36. Jacob T Schwartz. Probabilistic algorithms for verification of polynomial identities. In International Symposium on Symbolic and Algebraic Manipulation, pages 200-215. Springer, 1979. Google Scholar
  37. Amir Shpilka, Amir Yehudayoff, et al. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trendsregistered in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  38. Volker Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. Google Scholar
  39. Bernd Sturmfels. Algorithms in Invariant Theory. Texts &Monographs in Symbolic Computation. Springer, 2nd edition, 2008. Google Scholar
  40. David L. Wehlau. Constructive invariant theory for tori. Ann. Inst. Fourier (Grenoble), 43(4):1055-1066, 1993. URL: http://www.numdam.org/item?id=AIF_1993__43_4_1055_0.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact