Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties

DOI10.1137/080718115zbMath1168.03030arXivcs/0612134OpenAlexW1995509652MaRDI QIDQ3631907

No author found.

Publication date: 22 June 2009

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

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

zbMATH Keywords

computational complexitygeometric invariant theoryrepresentation theorylower boundsalgebraic geometry

Mathematics Subject Classification ID

Representation theory for linear algebraic groups (20G05) Geometric invariant theory (14L24) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (43)

Geometric aspects of iterated matrix multiplication ⋮ Rectangular Kronecker coefficients and plethysms in geometric complexity theory ⋮ \(P\) versus \(NP\) and geometry ⋮ Non-commutative Edmonds' problem and matrix semi-invariants ⋮ Cocharacter-closure and the rational Hilbert-Mumford theorem ⋮ Geometric complexity theory and matrix powering ⋮ Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture ⋮ 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 ⋮ Uniform Determinantal Representations ⋮ On vanishing of Kronecker coefficients ⋮ A diagrammatic approach to Kronecker squares ⋮ Covering \(\mathsf{Irrep}(S_n)\) with tensor products and powers ⋮ Kronecker products, characters, partitions, and the tensor square conjectures ⋮ Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient ⋮ The graph isomorphism problem and approximate categories ⋮ Eigenvalue distributions of reduced density matrices ⋮ Generalized Littlewood-Richardson coefficients for branching rules of \(\mathrm{GL}(n)\) and extremal weight crystals ⋮ On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions ⋮ Bounds on certain classes of Kronecker and \(q\)-binomial coefficients ⋮ Fundamental invariants of orbit closures ⋮ Padded Polynomials, Their Cousins, and Geometric Complexity Theory ⋮ Even partitions in plethysms. ⋮ Nonvanishing of Kronecker coefficients for rectangular shapes. ⋮ On the complexity of computing Kronecker coefficients ⋮ On the complexity of the permanent in various computational models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ No occurrence obstructions in geometric complexity theory ⋮ Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) ⋮ Rank and border rank of Kronecker powers of tensors and Strassen's laser method ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ A study of the representations supported by the orbit closure of the determinant ⋮ Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem ⋮ Connections between conjectures of Alon-Tarsi, Hadamard-Howe, and integrals over the special unitary group ⋮ Geometric complexity theory: an introduction for geometers ⋮ Unifying known lower bounds via geometric complexity theory ⋮ The Saxl conjecture and the dominance order

This page was built for publication: Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties