Abstract
The basis of geometric complexity theory is the essential equivalence between the foundational problems of Geometry (derandomization of Noether's Normalization Lemma for explicit varieties) and Complexity Theory (sub-exponential lower bounds for infinitesimally close approximation of exponential-time-computable multilinear polynomials by algebraic circuits). In view of this equivalence, the existing EXPSPACE vs. P gap, called the GCT chasm, in the complexity of derandomization of Noether's Normalization Lemma (NNL) for explicit varieties may be viewed as the common cause and measure of the difficulty of these problems.
This series of two tutorials will give an overview of these developments and of unconditional quasi-derandomization of NNL for some special cases of explicit varieties, including the one that was the focus of Hilbert's foundational paper in which Noether's Normalization Lemma was proved.
The second session of this talk will take place on Tuesday, September 16 from 10:20 am – 11:40 am.