No occurrence obstructions in geometric complexity theory

DOI10.1090/jams/908zbMath1401.68088arXiv1604.06431OpenAlexW2889385527WikidataQ129332102 ScholiaQ129332102MaRDI QIDQ4961749

Greta Panova, Peter Bürgisser, Christian Ikenmeyer

Publication date: 25 October 2018

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

representationsYoung tableauxorbit closuresplethysmstensorsgeometric complexity theoryhighest weight vectorspermanent versus determinant

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Representation theory for linear algebraic groups (20G05) Geometric invariant theory (14L24) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Equations for GL invariant families of polynomials ⋮ Vanishing symmetric Kronecker coefficients ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Uniform Determinantal Representations ⋮ Splitting Kronecker squares, 2-decomposition numbers, Catalan combinatorics, and the Saxl conjecture ⋮ Interview with Greta Panova ⋮ On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions ⋮ Fundamental invariants of orbit closures ⋮ The co-Pieri rule for stable Kronecker coefficients ⋮ On the complexity of the permanent in various computational models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The uniqueness of plethystic factorisation ⋮ On Various Multiplicity-Free Products of Schur Functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Binary determinantal complexity
• The boundary of the orbit of the 3-by-3 determinant polynomial
• Fundamental invariants of orbit closures
• Even partitions in plethysms.
• Nonvanishing of Kronecker coefficients for rectangular shapes.
• The complexity of computing the permanent
• Quadratic lower bound for permanent vs. determinant in any characteristic
• Some observations of plethysms
• \((\mathrm{GL}_n,\mathrm{GL}_m)\)-duality and symmetric plethysm
• On the ranks and border ranks of symmetric tensors
• Colorings and orientations of graphs
• Determining representations from invariant dimensions
• Completeness and reduction in algebraic complexity theory
• Geometric complexity theory and matrix powering
• On vanishing of Kronecker coefficients
• The complexity of factors of multivariate polynomials
• Plethysm and vertex operators
• Algebraic Geometry. I: Complex projective varieties.
• Hypersurfaces with degenerate duals and the geometric complexity theory program
• Cook's versus Valiant's hypothesis
• A lower bound for the determinantal complexity of a hypersurface
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• Characterizing Valiant's algebraic complexity classes
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Permanent versus determinant: Not via saturations
• On P vs. NP and geometric complexity theory
• An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• A study of the representations supported by the orbit closure of the determinant
• Padded Polynomials, Their Cousins, and Geometric Complexity Theory