Search Results

Documents authored by Panova, Greta

Document
DOI: 10.4230/LIPIcs.CCC.2026.28
Plethysm is in #BQP

Authors: Matthias Christandl, Aram W. Harrow, Greta Panova, Pietro M. Posta, and Michael Walter

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
Some representation-theoretic multiplicities, such as the Kostka and the Littlewood-Richardson coefficients, admit a combinatorial interpretation that places their computation in the complexity class #𝖯. Whether this holds more generally is considered an important open problem in mathematics and computer science, with relevance for geometric complexity theory and quantum information. Recent work has investigated the quantum complexity of particular multiplicities, such as the Kronecker coefficients and certain special cases of the plethysm coefficients. Here, we show that a broad class of representation-theoretic multiplicities is in #BQP. This includes the result that plethysm coefficients are in #BQP, which was only known in certain cases. It also implies all known results on the quantum complexity of previously studied coefficients as special cases, thus unifying, simplifying, and extending prior work. We obtain our result by multiple applications of the Schur transform; recent work has improved its dependence on the local dimension, which is crucial for our work. We further describe a general approach for showing that representation-theoretic multiplicities are in #BQP that captures the approaches of our and previous work. We complement the above by showing that the same multiplicities are also naturally in GapP and obtain polynomial-time classical algorithms when certain parameters are fixed.
Cite as

Matthias Christandl, Aram W. Harrow, Greta Panova, Pietro M. Posta, and Michael Walter. Plethysm is in #BQP. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 28:1-28:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{christandl_et_al:LIPIcs.CCC.2026.28,
  author =	{Christandl, Matthias and Harrow, Aram W. and Panova, Greta and Posta, Pietro M. and Walter, Michael},
  title =	{{Plethysm is in #BQP}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{28:1--28:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.28},
  URN =		{urn:nbn:de:0030-drops-270706},
  doi =		{10.4230/LIPIcs.CCC.2026.28},
  annote =	{Keywords: Quantum witness counting, #BQP, algebraic combinatorics, representation theory, representation-theoretic multiplicities}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.51
On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions

Authors: Julian Dörfler, Christian Ikenmeyer, and Greta Panova

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

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. We provide the first toy setting in which a separation can be achieved for a family of polynomials via these multiplicities. Mulmuley and Sohoni’s papers also conjecture that the vanishing behavior of 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ürgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. We provide first finite settings where a separation via multiplicities can be achieved, while the separation via occurrences is provably impossible. These settings are 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.
Cite as

Julian Dörfler, Christian Ikenmeyer, and Greta Panova. On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dorfler_et_al:LIPIcs.ICALP.2019.51,
  author =	{D\"{o}rfler, Julian and Ikenmeyer, Christian and Panova, Greta},
  title =	{{On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.51},
  URN =		{urn:nbn:de:0030-drops-106276},
  doi =		{10.4230/LIPIcs.ICALP.2019.51},
  annote =	{Keywords: Algebraic complexity theory, geometric complexity theory, Waring rank, plethysm coefficients, occurrence obstructions, multiplicity obstructions}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact