Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.03444 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916602210942976 |
|---|---|
| author | Berg, Maxim van den Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Lysikov, Vladimir |
| author_facet | Berg, Maxim van den Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Lysikov, Vladimir |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03444 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algebraic metacomplexity and representation theory Berg, Maxim van den Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Lysikov, Vladimir Computational Complexity Algebraic Geometry Representation Theory 68Q15, 20C35, 16S30 F.1.3 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. |
| title | Algebraic metacomplexity and representation theory |
| topic | Computational Complexity Algebraic Geometry Representation Theory 68Q15, 20C35, 16S30 F.1.3 |
| url | https://arxiv.org/abs/2411.03444 |