Computer Science/Discrete Mathematics Seminar I

The Geometric Complexity Theory (GCT) Program is an approach towards P versus NP and other lower bounds using algebraic geometry and representation theory. In this talk, we discuss how essentially all known algebraic circuit lower bounds and implications between lower bounds naturally fit into the representation-theoretic framework of GCT suggested in [GCT I, II, SIAM J. Comput.]. This includes the best known bounds on permanent versus determinant, lower bounds on constant depth circuits, the partial derivatives technique, the connected components technique, the degree bound, matrix rigidity, and others. In particular, we expose the representation-theoretic content of these proofs, introducing GCT from a new viewpoint as a natural unification of known results and a broad generalization of known techniques in complexity. This also shows that the framework of GCT is at least as powerful as previous methods, and gives many new proofs-of-concept that GCT can provide significant asymptotic complexity lower bounds. This new viewpoint also opens up the possibility of fruitful two-way interactions between previous techniques and the geometric and representation-theoretic methods of GCT; we provide several concrete suggestions of such interactions. No knowledge of algebraic geometry or representation theory is assumed - rather, we motivate the use and definitions of representation theory via these previous complexity-theoretic proofs.