geometric complexity theory

• Applicant: Dr. Christian Ikenmeyer
• Subject Area: Theoretical Computer Science
• Term: from 2018 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 408113219

• Final Report Year: 2023

Final Report Abstract

The flagship problem at the intersection of theoretical computer science and mathematics is the famous P vs NP problem. To work towards its solution Valiant introduced an algebraization in 1979 that is nowadays referred to as the determinant vs permanent problem. In 2001 Mulmuley and Sohoni reinterpreted this problem geometrically and founded geometric complexity theory (GCT), an approach towards fundamental computational complexity lower bounds via algebraic geometry, representation theory, and algebraic combinatorics. In this project we proved several fundamental results about the possibilities and limitations of GCT that deepen our understanding about the connections between computational complexity theory, algebraic geometry, and representation theory: We disproved a conjecture of Mulmuley on the existence of succinct encodings of generators of invariant rings, we answered Wigderson’s question on the NP-hardness of the orbit closure membership problem, we showed the difference in separational power of occurrence obstructions and multiplicity obstructions, which are two GCT methods for proving algebraic complexity lower bounds, we proved the NP-hardness of deciding the positivity of plethysm coefficients, we proved the #P-hardness of the evaluation of highest weight polynomials, and we showed how to get around these hardness issues by proving orbit closure separations that are based only on the symmetries of the polynomials. Moreover, we initiated a new research direction towards a rigorous understanding of combinatorial interpretations of representation theoretic quantities. Some of the questions are of independent interest in algebraic geometry and in representation theory. In the course of the project we developed several algorithms, implemented them, and made them available. We used them in our papers, but we also showed their viability for example by answering questions of Ranestad and Sturmfels. This software will be helpful for future projects on this and related topics. We have now arrived at clean homogeneous formulations of the determinant vs permanent and related questions, we have gained a deep understanding of the challenges of the GCT approach, and we have developed first small cases where we use the GCT separation method via multiplicity obstructions to prove algebraic complexity lower bounds.

Publications

• Algebraic branching programs, border complexity, and tangent spaces. In 35th Computational Complexity Confer- ence (CCC), 2020.
  M. Blaser; C. Ikenmeyer; M. Mahajan; A. Pandey & N. Saurabh
  
• Implementing geometric complexity theory: on the separation of orbit closures via symmetries. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 713-726. ACM.
  Ikenmeyer, Christian & Kandasamy, Umangathan
  
• On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions. SIAM Journal on Applied Algebra and Geometry, 4(2), 354-376.
  Dörfler, Julian; Ikenmeyer, Christian & Panova, Greta
  
• Search problems in algebraic complexity, GCT, and hardness of generators for invariant rings. In 35th Computational Complexity Conference (CCC), 2020.
  A. Garg; C. Ikenmeyer; V. Makam; R. Oliveira; M. Walter & A. Wigderson
  
• The Computational Complexity of Plethysm Coefficients. computational complexity, 29(2).
  Fischer, Nick & Ikenmeyer, Christian
  
• On the complexity of evaluating highest weight vectors. In 36th Computational Complexity Conference (CCC), 2021.
  M. Blaser, J. Dorfler & C. Ikenmeyer
  
• On the Orbit Closure Containment Problem and Slice Rank of Tensors. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2565-2584. Society for Industrial and Applied Mathematics.
  Bläser, Markus; Ikenmeyer, Christian; Lysikov, Vladimir; Pandey, Anurag & Schreyer, Frank-Olaf
  
• Young flattenings in the Schur module basis. accepted for EMS volume Varieties, Polyhedra, Computation, 2021.
  L. Haas & C. Ikenmeyer
  
• A note on VNP-completeness and border complexity. Information Processing Letters, 176, 106243.
  Ikenmeyer, Christian & Sanyal, Abhiroop
  
• Degree-restricted strength decompositions and algebraic branching programs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2022.
  F. Gesmundo; P. Ghosal; C. Ikenmeyer & V. Lysikov
  
• Equations for GL Invariant Families of Polynomials. Vietnam Journal of Mathematics, 50(2), 545-556.
  Breiding, Paul; Hodges, Reuven; Ikenmeyer, Christian & Michałek, Mateusz
  
• What is in #P and what is not?. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 860-871. IEEE.
  Ikenmeyer, Christian & Pak, Igor
  
• De-bordering and geometric complexity theory for Waring rank and related models. 2023.
  P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal & V. Lysikov
  
• Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3573-3586. Society for Industrial and Applied Mathematics.
  Ikenmeyer, Christian; Pak, Igor & Panova, Greta