Visu Makam, Institute for Advanced Study

Abstract

The Geometric Complexity Theory (GCT) program is an algebro-geometric approach to the celebrated P vs NP problem. Connections between GCT and classical subject of invariant theory have been uncovered in the last decade. In particular, GCT (morally) predicts many complexity-theoretic statements in invariant theory. In this context, Mulmuley conjectures (in great generality) that generators for invariant rings can be packed into succinct circuits. In this talk, we will give counterexamples to this conjecture. This talk will be accessible to graduate students and will not assume any familiarity with invariant theory or GCT.