Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Wednesday, April 24, 2013 - 3:00pm to 4:00pm
Michael Forbes

Polynomial identity testing asks whether a given algebraic circuit C computes
the identically zero polynomial. Randomized algorithms are known for this
problem, via the Schwartz-Zippel lemma, and in recent years there has been
much effort to find a deterministic algorithm, even for restricted types of
circuits C. Such algorithms would have several algorithmic applications, as
well as implications for circuit lower bounds.

Mulmuley recently observed that the "Noether Normalization Lemma" of
commutative-algebra/algebraic-geometry can be "derandomized" assuming a
deterministic algorithm for polynomial identity testing, and argued that this
is further evidence that constructing such algorithms are hard. He also
conjectured that the specific case of Noether Normalization (for "matrices
under simultaneous conjugation") would still be hard. In this work, we
derandomize this specific case of Noether Normalization, using a recent
polynomial identity testing algorithm of the authors for the class of
read-once oblivious algebraic branching programs.

Joint work with Amir Shpilka.

Relevant URL(S): http://www.mit.edu/~ecprice/algcompsem/
For more information please contact: Eric Price, ecprice@mit.edu