Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
From MaRDI portal
Publication:2784468
DOI10.1137/S009753970038715XzbMath0992.03048OpenAlexW2074207216MaRDI QIDQ2784468
No author found.
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s009753970038715x
stabilitycomputational complexitygeometric invariant theoryrepresentation theoryalgebraic geometrycircuit sizeformula sizeinfinitesimal neighborhoodspartially stable point
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
A note on VNP-completeness and border complexity ⋮ The boundary of the orbit of the 3-by-3 determinant polynomial ⋮ Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory ⋮ Torsion points and matrices defining elliptic curves ⋮ Rectangular Kronecker coefficients and plethysms in geometric complexity theory ⋮ Lower bounds for the circuit size of partially homogeneous polynomials ⋮ SIMPLE GROUPS STABILIZING POLYNOMIALS ⋮ \(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 ⋮ Vanishing symmetric Kronecker coefficients ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Quantum mechanics of bipartite ribbon graphs: integrality, lattices and Kronecker coefficients ⋮ Permanent versus determinant: Not via saturations ⋮ Uniform Determinantal Representations ⋮ Necessary conditions for the positivity of Littlewood-Richardson and plethystic coefficients ⋮ A diagrammatic approach to Kronecker squares ⋮ Ranks of linear matrix pencils separate simultaneous similarity orbits ⋮ The quantum detection of projectors in finite-dimensional algebras and holography ⋮ On the closures of monotone algebraic classes and variants of the determinant ⋮ Tropical Fano schemes ⋮ Holographic algorithms beyond matchgates ⋮ 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 ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ Generalized counting constraint satisfaction problems with determinantal circuits ⋮ On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions ⋮ A geometric approach to the Kronecker problem. I: The two row case. ⋮ Complexity classes and completeness in algebraic geometry ⋮ Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling ⋮ Plethysm and lattice point counting ⋮ Fundamental invariants of orbit closures ⋮ Obstructions to combinatorial formulas for plethysm ⋮ Padded Polynomials, Their Cousins, and Geometric Complexity Theory ⋮ Even partitions in plethysms. ⋮ Nonvanishing of Kronecker coefficients for rectangular shapes. ⋮ 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 ⋮ The uniqueness of plethystic factorisation ⋮ Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) ⋮ A Note on normalizations of orbit closures ⋮ Determinant Equivalence Test over Finite Fields and over Q ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ A study of the representations supported by the orbit closure of the determinant ⋮ Linear projections of the Vandermonde polynomial ⋮ Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem ⋮ Integrality, duality and finiteness in combinatoric topological strings ⋮ Connections between conjectures of Alon-Tarsi, Hadamard-Howe, and integrals over the special unitary group ⋮ A complexity theory of constructible functions and sheaves ⋮ Kronecker coefficients for some near-rectangular partitions ⋮ Geometric complexity theory: an introduction for geometers ⋮ Two orbits: when is one in the closure of the other? ⋮ Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case ⋮ Unifying known lower bounds via geometric complexity theory ⋮ The Saxl conjecture and the dominance order ⋮ Membership in Moment Polytopes is in NP and coNP ⋮ All-orders asymptotics of tensor model observables from symmetries of restricted partitions
This page was built for publication: Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
