English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

On Geometric Complexity Theory: Multiplicity Obstructions are Stronger than Occurrence Obstructions

MPS-Authors
/persons/resource/persons202366

Ikenmeyer,  Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1901.04576.pdf
(Preprint), 401KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Dörfler, J., Ikenmeyer, C., & Panova, G. (2019). On Geometric Complexity Theory: Multiplicity Obstructions are Stronger than Occurrence Obstructions. Retrieved from http://arxiv.org/abs/1901.04576.


Cite as: http://hdl.handle.net/21.11116/0000-0003-B393-C
Abstract
Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. The papers also conjecture that the vanishing behavior of these multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and B\"urgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. This paper provides for the first time a setting where separating with multiplicities can be achieved, while the separation with occurrences is provably impossible. Our setting is surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite's reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases.