License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.12
URN: urn:nbn:de:0030-drops-125645
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12564/
Go to the corresponding LIPIcs Volume Portal

Garg, Ankit ; Ikenmeyer, Christian ; Makam, Visu ; Oliveira, Rafael ; Walter, Michael ; Wigderson, Avi

Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings

pdf-format:
LIPIcs-CCC-2020-12.pdf (0.6 MB)

Abstract

We 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(ℂ)-representations. We provide simple examples that disprove this conjecture (under standard complexity assumptions).
We develop a general framework, denoted 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.

BibTeX - Entry

@InProceedings{garg_et_al:LIPIcs:2020:12564,
  author =	{Ankit Garg and Christian Ikenmeyer and Visu Makam and Rafael Oliveira and Michael Walter and Avi Wigderson},
  title =	{{Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12564},
  URN =		{urn:nbn:de:0030-drops-125645},
  doi =		{10.4230/LIPIcs.CCC.2020.12},
  annote =	{Keywords: generators for invariant rings, succinct encodings}
}

Keywords: generators for invariant rings, succinct encodings
Collection: 35th Computational Complexity Conference (CCC 2020)
Issue Date: 2020
Date of publication: 17.07.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI