Help Privacy Policy Disclaimer
  Advanced SearchBrowse





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


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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 401KB

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

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: https://hdl.handle.net/21.11116/0000-0003-B393-C
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.