ECCC-Report TR13-033https://eccc.weizmann.ac.il/report/2013/033Comments and Revisions published for TR13-033en-usThu, 07 Mar 2013 21:24:14 +0200
Revision 1
| Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing |
Michael Forbes,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2013/033#revision1Mulmuley 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.Thu, 07 Mar 2013 21:24:14 +0200https://eccc.weizmann.ac.il/report/2013/033#revision1
Paper TR13-033
| Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing |
Michael Forbes,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2013/033Mulmuley 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.
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.
Also, as a consequence of our work we give a deterministic parallel polynomial-time algorithm for deciding if two matrix tuples have intersecting orbit closures, under simultaneous conjugation. We also show that the corresponding problem for (non-closed) orbits is reducible to PIT of ABPs, and thus solvable in randomized parallel polynomial-time.
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.
Fri, 01 Mar 2013 10:51:17 +0200https://eccc.weizmann.ac.il/report/2013/033