Membership in Moment Polytopes is in NP and coNP

DOI10.1137/15M1048859zbMath1371.68105arXiv1511.03675OpenAlexW2254435734MaRDI QIDQ5269822

Peter Bürgisser, Michael Walter, Matthias Christandl, Ketan D. Mulmuley

Publication date: 28 June 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.03675

zbMATH Keywords

computational complexityquantum information theoryKronecker coefficientsasymptotic representation theorymoment polytopequantum marginal problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Representations of Lie algebras and Lie superalgebras, algebraic theory (weights) (17B10) Finite-dimensional groups and algebras motivated by physics and their representations (81R05) Momentum maps; symplectic reduction (53D20)

Related Items

The Horn inequalities from a geometric point of view, Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory, On vanishing of Kronecker coefficients, Quantum marginals from pure doubly excited states

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric invariant theory and generalized eigenvalue problem. II
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Eigenvalue distributions of reduced density matrices
• The spectra of quantum states and the Kronecker coefficients of the symmetric group
• Nonzero Kronecker coefficients and what they tell us about spectra
• Classical Bruhat orders and lexicographic shellability
• A basis for representations of symplectic Lie algebras
• On vanishing of Kronecker coefficients
• Inequalities for moment cones of finite-dimensional representations
• Quantum state transformations and the Schubert calculus
• Convexity properties of the moment mapping. III
• The Pauli principle revisited
• Polynomial bounds for rings of invariants
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Entanglement Polytopes: Multiparticle Entanglement from Single-Particle Information
• Gelfand–Tsetlin Bases for Classical Lie Algebras
• Quantum Computation and Quantum Information
• An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
• A Stratification of the Null Cone Via the Moment Map
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Convexity and Commuting Hamiltonians
• On convexity, the Weyl group and the Iwasawa decomposition
• Combinatorial Nullstellensatz
• Coadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion
• Lie Groups, Lie Algebras, and Representations
• Deciding Positivity of Littlewood--Richardson Coefficients
• Geometric complexity theory and tensor rank
• Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix
• Computational Complexity