ECCC-Report TR19-140https://eccc.weizmann.ac.il/report/2019/140Comments and Revisions published for TR19-140en-usWed, 19 Feb 2020 15:14:42 +0200
Revision 1
| Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. |
Rafael Mendes de Oliveira,
Ankit Garg,
Visu Makam,
Avi Wigderson,
Christian Ikenmeyer,
Michael Walter
https://eccc.weizmann.ac.il/report/2019/140#revision1We 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(\C)$-representations. We provide simple examples that disprove this conjecture (under standard complexity assumptions).
We develop a general framework, denoted \emph{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.Wed, 19 Feb 2020 15:14:42 +0200https://eccc.weizmann.ac.il/report/2019/140#revision1
Paper TR19-140
| Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. |
Rafael Mendes de Oliveira,
Ankit Garg,
Visu Makam,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2019/140We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).Fri, 11 Oct 2019 01:51:47 +0300https://eccc.weizmann.ac.il/report/2019/140