Geometric Complexity Theory: an introduction for geometers
Preprint
Abstract
This is survey of recent developments in, and a tutorial on, the approach to P v. NP and related questions called Geometric Complexity Theory (GCT). The article is written to be accessible to graduate students. Numerous open questions in algebraic geometry and representation theory relevant for GCT are presented.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and pfaffiansAdvances in Applied Mathematics, 2013
- Arithmetic circuits: The chasm at depth four gets widerTheoretical Computer Science, 2012
- Equations for secant varieties of Veronese and other varietiesAnnali di Matematica Pura ed Applicata (1923 -), 2011
- versusand geometryJournal of Symbolic Computation, 2010
- Characterizing Valiant's algebraic complexity classesJournal of Complexity, 2008
- Depth-3 arithmetic circuits over fields of characteristic zerocomputational complexity, 2001
- Lower bounds on arithmetic circuits via partial derivativescomputational complexity, 1996
- On the relations of various conjectures on Latin squares and straightening coefficientsDiscrete Mathematics, 1994
- Stable properties of plethysm : on two conjectures of Foulkesmanuscripta mathematica, 1993
- Gaussian maps and tensor products of irreducible representationsmanuscripta mathematica, 1991