An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP

Abstract

We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the Geometric Complexity Theory program to prove a variant of Valiant's algebraic analog of the P not equal to NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate.

29 pages, v2: role of symmetric Kronecker coefficients explained

References in corpus (10)

• Quantum marginal problem and representations of the symmetric group
• Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
• Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
• Nonvanishing of Kronecker coefficients for rectangular shapes
• Even Partitions in Plethysms
• Geometric Complexity Theory VII: Nonstandard quantum group for the plethysm problem
• Geometric Complexity Theory V: On deciding nonvanishing of a generalized Littlewood-Richardson coefficient
• Geometric Complexity Theory and Tensor Rank
• Two orbits: When is one in the closure of the other?
• A note on certain Kronecker coefficients

Cited by in corpus (8)

• On vanishing of Kronecker coefficients
• Introduction to twisted commutative algebras
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Nonvanishing of Kronecker coefficients for rectangular shapes
• Even Partitions in Plethysms
• Hypersurfaces with degenerate duals and the Geometric Complexity Theory Program
• Geometric Complexity Theory and Tensor Rank
• On rectangular Kronecker coefficients