Geometric Complexity Theory: an introduction for geometers
arXiv:1305.7387
Abstract
This article is a survey of recent developments in, and a tutorial on, the approach to P v. NP and related questions called Geometric Complexity Theory (GCT). It is written to be accessible to graduate students. Numerous open questions in algebraic geometry and representation theory relevant for GCT are presented.
arXiv comment40 pages, v2: many small errors fixed thanks to careful readings by M. Brion, P. Burgisser and R. Tange, v3: 42 pages, more detail added regarding shallow circuits
References in corpus (6)
- Simple groups stabilizing polynomials
- New lower bounds for the border rank of matrix multiplication
- Hypersurfaces with degenerate duals and the Geometric Complexity Theory Program
- Arithmetic circuits: the chasm at depth four gets wider
- Padded polynomials, their cousins, and geometric complexity theory
- Complexity of linear circuits and geometry