An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to \mathbf{VP}\neq\mathbf{VNP}

DOI10.1137/090765328zbMATH Open1252.68134OpenAlexW2007051555MaRDI QIDQ3096098FDOQ3096098

J. M. Landsberg, Laurent Manivel, Jerzy Weyman, Peter Bürgisser

Publication date: 7 November 2011

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

Full work available at URL: https://doi.org/10.1137/090765328

zbMATH Keywords

determinantgeometric invariant theorypermanentgeometric complexity theoryorbit closureKronecker coefficientP vs. NP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symmetric groups (20B30) Geometric invariant theory (14L24) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Cited In (34)

• A complexity theory of constructible functions and sheaves
• The Horn inequalities from a geometric point of view
• Rectangular symmetries for coefficients of symmetric functions
• A note on certain Kronecker coefficients
• A diagrammatic approach to Kronecker squares
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• On vanishing of Kronecker coefficients
• A note on VNP-completeness and border complexity
• The Saxl conjecture and the dominance order
• Exponential varieties
• Geometric aspects of iterated matrix multiplication
• Connections between conjectures of Alon-Tarsi, Hadamard-Howe, and integrals over the special unitary group
• On the asymptotics of Kronecker coefficients.
• Splitting Kronecker squares, 2-decomposition numbers, Catalan combinatorics, and the Saxl conjecture
• Padded Polynomials, Their Cousins, and Geometric Complexity Theory
• \(P\) versus \(NP\) and geometry
• Permanent versus determinant: Not via saturations
• Eigenvalue distributions of reduced density matrices
• Even partitions in plethysms.
• Unifying known lower bounds via geometric complexity theory
• Non-commutative Edmonds' problem and matrix semi-invariants
• Bounded-rank tensors are defined in bounded degree
• Geometric complexity theory and matrix powering
• Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
• Geometric complexity theory: an introduction for geometers
• No occurrence obstructions in geometric complexity theory
• A study of the representations supported by the orbit closure of the determinant
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• The partition algebra and the plethysm coefficients. II: Ramified plethysm
• Plethysm and lattice point counting
• Vanishing symmetric Kronecker coefficients
• Title not available (Why is that?)
• Fundamental invariants of orbit closures
• Membership in Moment Polytopes is in NP and coNP

This page was built for publication: An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3096098)