Algebraic Geometry Fellows' Seminar

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.