For more information about this meeting, contact 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 |