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

DOI10.1137/090765328zbMath1252.68134OpenAlexW2007051555MaRDI QIDQ3096098

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

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

geometric invariant theory determinant permanent geometric complexity theory orbit closure Kronecker coefficient P vs. NP

Mathematics Subject Classification ID

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

Related Items (32)

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