Geometrische Komplexitätstheorie

• Antragsteller: Dr. Christian Ikenmeyer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 408113219

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Das wohl bekannteste Problem im Schnittbereich von theoretischer Informatik und Mathematik ist das berühmte P-NP-Problem. Um einer Lösung näher zu kommen, führte Valiant 1979 eine Algebraisierung von P-NP ein, welche heute als das Determinante-vs-Permanente-Problem bekannt ist. Mulmuley und Sohoni interpretierten dieses Problem 2001 geometrisch und gründeten die geometrische Komplexitätstheorie (GCT), einen Ansatz, um fundamentale untere Kom­ plexitätsschranken mittels algebraischer Geometrie, Darstellungstheorie und algebraischer Kombina­ torik zu beweisen. Im Rahmen dieses Projektes bewiesen wir mehrere grundlegende Resultate über die Möglichkeiten und Grenzen von GCT, welche zu einem tieferen Verständnis der Verbindungen zwischen Komplexitätstheorie, algebraischer Geometrie und Darstellungstheorie führen: Wir widerlegten eine Vermutung von Mulmuley über kompakte Kodierungen von Erzeugern von lnvarianteningen, wir beantworteten Wigdersons Frage zur NP-Schwere des Bahnabschlusszugehörigkeitsproblems, wir zeigten den Unterschied der Trennschärfe von Occurrence Obstructions und Multiplicity Obstructions, welches zwei Methoden der GCT zum Zeigen unterer Schranken in algebraischen Berechnungsmodellen sind, wir bewiesen die NP-Schwere des Entscheidens der Positivität von Plethysmenkoeffizienten, wir bewiesen die #P-Schwere der Auswertung von Höchstgewichtspolynomen, und wir zeigten, wie man diese Schwere-Probleme umgehen kann, indem wir Bahnabschlusstrennungen bewiesen, welche nur auf den Symmetrien der Polynome beruhen. Zudem initiierten wir eine neue Forschungsrichtung für das mathematisch rigorose Verständnis kombinatorischer Interpretationen von darstellungstheoretischen Größen. Einige der von uns beantworteten Fragen sind von unabhängigem Interesse in der algebraischen Geometrie und der Darstellungstheorie. Im laufe des Projektes entwickelten wir mehrere Algorithmen, implementierten sie und machten sie öffentlich zugänglich. Wir nutzten sie in unseren Arbeiten, aber wir stellten ihre Brauchbarkeit auch noch anders unter Beweis, indem wir zum Beispiel Fragen von Ranestad und Sturmfels beantworteten. Diese Software wird hilfreich für zukünftige Projekte in diesem oder verwandten Themen sein. Wir sind nun an einem Punkt angelangt, wo wir saubere homogene Formulierungen des Determinante-vs-Permanente-Problems und verwandter Fragen haben; wir haben ein tiefes Verständnis des GCT-Ansatzes erlangt, und wir haben erste kleine Fälle erarbeitet, wo wir die GCT-Trennmethode mittels Multiplicity Obstructions benutzen, um untere Schranken in algebraischen Berechnungsmodellen zu zeigen.

Projektbezogene Publikationen (Auswahl)

• 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