Geometric complexity theory. V: Efficient algorithms for Noether normalization

DOI10.1090/JAMS/864MaRDI QIDQ2826783zbMATH OpenOpenAlexFDO

Authors Ketan D. Mulmuley

Publication date 18 October 2016

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

geometric complexity theoryNoether normalizationexplicit varieties

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: We study a basic algorithmic problem in algebraic geometry, which we call NNL, of constructing a normalizing map as per Noether's Normalization Lemma. For general explicit varieties, as formally defined in this paper, we give a randomized polynomial-time Monte Carlo algorithm for this problem. For some interesting cases of explicit varieties, we give deterministic quasi-polynomial time algorithms. These may be contrasted with the standard EXPSPACE-algorithms for these problems in computational algebraic geometry. In particular, we show that: (1) The categorical quotient for any finite dimensional representation $V$ of $S{L}_m$, with constant $m$, is explicit in characteristic zero. (2) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in the dimension of $V$. (3) The categorical quotient of the space of $r$-tuples of $mimesm$ matrices by the simultaneous conjugation action of $S{L}_m$ is explicit in any characteristic. (4) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in $m$ and $r$ in any characteristic $p$ not in $[2,m/2]$. (5) NNL for every explicit variety in zero or large enough characteristic can be solved deterministically in quasi-polynomial time, assuming the hardness hypothesis for the permanent in geometric complexity theory. The last result leads to a geometric complexity theory approach to put NNL for every explicit variety in P.

Recommendations

• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• scientific article; zbMATH DE number 4101329
• On the computation of Noether normalization
• Efficient Algorithms for Computing Nœther Normalization
• Geometric complexity theory. I: An approach to the P vs. NP and related problems

Cites work

• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 3970973 (Why is no real title available?)
• scientific article; zbMATH DE number 3751115 (Why is no real title available?)
• scientific article; zbMATH DE number 51906 (Why is no real title available?)
• scientific article; zbMATH DE number 3508744 (Why is no real title available?)
• scientific article; zbMATH DE number 3563286 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 482758 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 1950436 (Why is no real title available?)
• scientific article; zbMATH DE number 1996521 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 1870513 (Why is no real title available?)
• scientific article; zbMATH DE number 3029489 (Why is no real title available?)
• A Selection of Lower Bounds for Arithmetic Circuits
• A taxonomy of problems with fast parallel algorithms
• Algebraic Geometry. I: Complex projective varieties.
• Algorithms in invariant theory
• An overview of mathematical issues arising in the geometric complexity theory approach to \(\mathbf{VP}\neq\mathbf{VNP}\)
• An upper bound for the length of a finite-dimensional algebra
• Arithmetic circuits and the Hadamard product of polynomials
• Arithmetic circuits: a survey of recent results and open questions
• Boundaries of VP and VNP
• Characterizing Valiant's algebraic complexity classes
• Completeness and reduction in algebraic complexity theory
• Computational Complexity
• Computational invariant theory. With two appendices by Vladimir L. Popov and an addendum by Nobert A. Campo and Vladimir L. Popov
• Computing bases for rings of permutation-invariant polynomials
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic polynomial identity testing in non-commutative models
• Diagonal Circuit Identity Testing and Lower Bounds
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Fast Parallel Computation of Polynomials Using Few Processors
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem
• Geometric Invariant Theory
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Hardness vs randomness
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Hypersurfaces with degenerate duals and the geometric complexity theory program
• Improved Polynomial Identity Testing for Read-Once Formulas
• Invariants of several matrices
• Lower Bounds in a Parallel Model without Bit Operations
• MODULI OF REPRESENTATIONS OF FINITE DIMENSIONAL ALGEBRAS
• Multivariate polynomials, duality, and structured matrices
• New results on quantifier elimination over real closed fields and applications to constraint databases
• On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna
• On the Foundations of Combinatorial Theory: IX Combinatorial Methods in Invariant Theory
• Polynomial bounds for rings of invariants
• Polynomial degree bounds for matrix semi-invariants
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
• Rationale quasihomogene Singularitäten
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• Representations of quivers.
• Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients
• Semi-invariants of quivers as determinants
• Semisimple Representations of Quivers
• Sharp Effective Nullstellensatz
• Singularités rationnelles et quotients par les groupes réductifs. (Rational singularities and quotients by reductive groups)
• Space-efficient Gröbner basis computation without degree bounds
• Standard monomial theory. Invariant theoretic approach
• TRACE IDENTITIES OF FULL MATRIX ALGEBRAS OVER A FIELD OF CHARACTERISTIC ZERO
• Tame and wild matrix problems
• The Historical Development of Algebraic Geometry
• The complexity of computing the permanent
• The complexity of factors of multivariate polynomials
• The invariant theory of n n matrices
• The multivariate resultant is NP-hard in any characteristic
• Unifying known lower bounds via geometric complexity theory

Cited in

(27)

• Polystability in positive characteristic and degree lower bounds for invariant rings
• Generalized Littlewood-Richardson coefficients for branching rules of \(\mathrm{GL}(n)\) and extremal weight crystals
• scientific article; zbMATH DE number 7250150 (Why is no real title available?)
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• Effective normalization of a nonsingular in codimension one algebraic variety
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• Variety evasive subspace families
• Hitting sets for orbits of circuit classes and polynomial families
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Optimization, complexity and invariant theory (invited talk)
• Towards blackbox identity testing of log-variate circuits
• scientific article; zbMATH DE number 2112254 (Why is no real title available?)
• Maximum likelihood estimation for matrix normal models via quiver representations
• General linear group action on tensors: a candidate for post-quantum cryptography
• Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
• Complexity of robust orbit problems for torus actions and the abc-conjecture
• scientific article; zbMATH DE number 7561740 (Why is no real title available?)
• Algorithms for orbit closure separation for invariants and semi-invariants of matrices
• A generalized sylvester-gallai type theorem for quadratic polynomials
• Efficient Algorithms for Computing Nœther Normalization
• Ranks of linear matrix pencils separate simultaneous similarity orbits
• Weyl's polarization theorem in positive characteristic
• On the power of border width-2 ABPs over fields of characteristic 2
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces

This page was built for publication: Geometric complexity theory. V: Efficient algorithms for Noether normalization

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