Explicit Noether normalization for simultaneous conjugation via polynomial identity testing

DOI10.1007/978-3-642-40328-6_37MaRDI QIDQ2851883zbMATH OpenOpenAlexFDO

Authors Amir Shpilka, Michael A. Forbes

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Abstract: Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In this work, we show this is not the case. That is, we improve Mulmuley's reduction and correspondingly weaken the conjecture regarding PIT needed to give explicit Noether Normalization. We then observe that the weaker conjecture has recently been nearly settled by the authors, who gave quasipolynomial size hitting sets for the class of read-once oblivious algebraic branching programs (ROABPs). This gives the desired explicit Noether Normalization unconditionally, up to quasipolynomial factors. As a consequence of our proof we give a deterministic parallel polynomial-time algorithm for deciding if two matrix tuples have intersecting orbit closures, under simultaneous conjugation. We also study the strength of conjectures that Mulmuley requires to obtain similar results as ours. We prove that his conjectures are stronger, in the sense that the computational model he needs PIT algorithms for is equivalent to the well-known algebraic branching program (ABP) model, which is provably stronger than the ROABP model. Finally, we consider the depth-3 diagonal circuit model as defined by Saxena, as PIT algorithms for this model also have implications in Mulmuley's work. Previous work have given quasipolynomial size hitting sets for this model. In this work, we give a much simpler construction of such hitting sets, using techniques of Shpilka and Volkovich.

Recommendations

• Depth-4 identity testing and Noether's normalization lemma
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• Deterministic polynomial identity testing in non-commutative models
• Near-optimal bootstrapping of hitting sets for algebraic circuits
• Geometry of orbits of permanents and determinants

Cited in

(23)

• Blackbox identity testing for sum of special ROABPs and its border class
• Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
• Improved hitting set for orbit of ROABPs
• Polystability in positive characteristic and degree lower bounds for invariant rings
• An exponential lower bound for the degrees of invariants of cubic forms and tensor actions
• Algorithms for orbit closure separation for invariants and semi-invariants of matrices
• Operator scaling: theory and applications
• Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• Efficient Algorithms for Computing Nœther Normalization
• Towards blackbox identity testing of log-variate circuits
• A generalized sylvester-gallai type theorem for quadratic polynomials
• scientific article; zbMATH DE number 7561740 (Why is no real title available?)
• Depth-4 identity testing and Noether's normalization lemma
• Connections between graphs and matrix spaces
• scientific article; zbMATH DE number 7758310 (Why is no real title available?)
• Interactions of computational complexity theory and mathematics
• Variety evasive subspace families
• Complexity of robust orbit problems for torus actions and the abc-conjecture
• Towards identity testing for sums of products of Read-once and multilinear bounded-Read formulae
• Hitting sets for orbits of circuit classes and polynomial families
• Uniform bounds on product Sylvester-Gallai configurations
• Derandomization and absolute reconstruction for sums of powers of linear forms

This page was built for publication: Explicit Noether normalization for simultaneous conjugation via polynomial identity testing

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