Fall 2014

Algebraic Geometry Fellows' Seminar

Add to Calendar


Michael Forbes (Massachusetts Institute of Technology)


Calvin Lab 116

Explicit Dimension Reduction for Varieties, and the Polynomial Identity Testing Problem

We consider the task of mapping a large-dimensional ambient space C^n to small-dimension ambient space C^m (with m<<n, so that C is the complex numbers), so that a given variety X inside C^n of dimension ~m has its "relevant" properties preserved under this map.  In particular, a random linear map from C^n → C^m would suffice in many instances.  Our challenge is to deterministically and efficiently construct such a linear map for interesting varieties.

In particular, (Mulmuley 2012) observed that for all "explicit" varieties this task is equivalent to the problem of developing deterministic algorithms for the _polynomial identity testing (PIT)_ problem: given an algebraic circuit, decide whether this circuit computes the zero polynomial.  Developing deterministic algorithms for this problem is challenging problem in general.

I shall define the PIT problem, explain how it instantiates the quest for explicit dimension reduction, and highlight why it is a challenging problem in general.  I will then define the ring of invariants for simultaneous conjugation of an r-tuple of (n x n)-matrices and instantiate Mulmuley's result in this case, showing how one can express dimension reduction for this ring in the language of PIT.  I will then show how a deterministic PIT algorithm of (Forbes and Shpilka 2013) can give a near-solution to explicit dimension reduction for this ring.