| Theory Group, Department of Computer Science, University of Chicago | ||
| |
Theory Seminar Our seminar is intended to be broad and will (hopefully) cover not only what is traditionally referred to as "core theory", but also many topics at least distantly related to it. And when we are really interested in a result and/or a speaker, the employed notion of distance will be understood rather liberally! Logistically, our normal meeting time and place is: Ryerson 251 (refreshments are served before the seminar). But, as a courtesy to our out-of-town speakers, we expect to meet occasionally on a different day, read the announcements carefully (and sign to our mailing list if you want to receive them on a regular basis).
The list of people who already expressed interest in speaking at our seminar includes Program (in order to read abstract, click on the title)
September 15: Jin-Yi Cai (University of Wisconsin), A Dichotomy Theorem for Graph Homomorphisms with Complex Values
October 5, 3:45pm: Dieter van Melkebeek (University of
Wisconsin), Satisfiability Allows No Nontrivial Sparsification Unless The
Polynomial-Time Hierarchy Collapses
October 13: no seminar (Dagstuhl workshop on algebraic methods in computational complexity) October 20: Janos Simon (University of Chicago), Sorting by Random Insertion October 27: no seminar (50th Annual IEEE Symposium on Foundations of Computer Science)
November 3: Anastasios Sidiropoulos (TTI-C), Graph Genus and Random Partitions
November 10: Paul Beame (University of Washington), Hardness Amplification in Proof Complexity
November 23, 3:45pm: Joseph Landsberg (Texas A&M University), Mathematical Aspects of the Geometric Complexity Theory
Approach to P Versus NP
December 1: Amir Yehudayoff (IAS), Algebraic complexity with less relations
January 12: Gregory Shakhnarovich (TTI-C)
January 19: Silvio Micali (MIT)
February 16: Valentine Kabanets (IAS and SFU)
|
|