PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Karl Schwede, Robert Vaughan, Mihran Papikian, Ae Ja Yee.

Title:Unifying known lower bounds via geometric complexity theory
Seminar:Algebra and Number Theory Seminar
Speaker:Josh Grochow, University of Toronto
Abstract:
Geometric Complexity Theory (GCT) is a program to resolve major open questions in complexity theory such as P vs NP, using algebraic geometry and representation theory. Although GCT was developed as a long-term program aimed primarily at P vs NP and permanent versus determinant, in this talk we show that essentially all known arithmetic circuit lower bounds and implications between lower bounds naturally fit into the representation-theoretic framework suggested by GCT. That is, the original proofs, with what is often just a little extra work, already provide representation-theoretic obstructions in the sense of GCT for their respective lower bounds. This enables us to expose a new viewpoint on GCT, whereby it is a natural unification of known results and broad generalization of known techniques in complexity. It 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 indeed provide significant asymptotic complexity lower bounds. This new viewpoint also opens up the possibility of fruitful two-way interactions between previous results and the geometric and representation-theoretic methods of GCT; we provide several concrete suggestions of such interactions. This talk will assume essentially no background in complexity theory.

Room Reservation Information

Room Number:MB106
Date:12 / 05 / 2013
Time:11:15am - 12:05pm