DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2025.26

Algebraic Metacomplexity and Representation Theory

Authors: Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, and Vladimir Lysikov

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract

In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. We use this to resolve an open question posed by Grochow, Kumar, Saks & Saraf (2017). Our result means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, it means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincaré-Birkhoff-Witt theorem for Lie algebras and on Gelfand-Tsetlin theory, for which we give the necessary comprehensive background.

Cite as

Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, and Vladimir Lysikov. Algebraic Metacomplexity and Representation Theory. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 26:1-26:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vandenberg_et_al:LIPIcs.CCC.2025.26,
  author =	{van den Berg, Maxim and Dutta, Pranjal and Gesmundo, Fulvio and Ikenmeyer, Christian and Lysikov, Vladimir},
  title =	{{Algebraic Metacomplexity and Representation Theory}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{26:1--26:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.26},
  URN =		{urn:nbn:de:0030-drops-237209},
  doi =		{10.4230/LIPIcs.CCC.2025.26},
  annote =	{Keywords: Algebraic complexity theory, metacomplexity, representation theory, geometric complexity theory}
}

Search Results

Documents authored by van den Berg, Maxim

Algebraic Metacomplexity and Representation Theory

Abstract

Cite as

Thanks for your feedback!

Could not send message