Theory Seminar 2009 Academic Year
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. Note non-standard day and time!
October 20: Janos Simon (University of Chicago), Sorting by Random Insertion.
November 3: Anastasios Sidiropoulos (TTIC), 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. Note non-standard day and time!
December 1: Amir Yehudayoff (IAS), Algebraic complexity with less relations.
January 12: Gregory Shakhnarovich (TTIC), Supervised Learning of Similarity.
January 19: Silvio Micali (MIT), Resilient Mechanism Design.
January 26: Laszlo Babai (University of Chicago), Polynomial-time Theory of Matrix Groups.
February 2: Julia Chuzhoy (TTIC), Allocating Goods to Maximize Fairness.
February 9: Sergey Yekhanin (Microsoft Research Silicon Valley), Matching Vector Codes.
February 16: Valentine Kabanets (IAS and SFU), Direct-Product Decoding and Testing, and 2-query PCPs.
February 23: Parinya Chalermsook (University of Chicago), Resource Minimization for Fire Containment.
March 2: Benjamin Rossman (MIT), Lower Bounds for k-CLIQUE on Random Graphs.
March 9: Andrew Lyons (Argonne National Lab), Tight Lower Bounds on the Complexity of Derivative Accumulation.
March 16, 11am, TTIC, Room 526: Mohammad Hossein Bateni (Princeton University), PTAS for Planar Steiner Forest. Note non-standard time and place!
March 30: Aaron Bernstein (MIT), Improved Approximation Algorithms for Dynamic Shortest Paths: Breaking Through the O(n) Update Time Barrier.
April 6: James Lee (University of Washington), Cover times, blanket times, and majorizing measures.
April 13: YouMing Qiao (Tsinghua University and U of Chicago), Pseudorandom Generators for Polynomial Identity Testing.
April 20: Hamed Hatami (Princeton University), Uniformity and Testing Correlations in $F_p^n$.
April 27: Jason Hartline (Northwestern University), Multi-dimensional Mechanism Design and Sequential Posted Pricing.
May 4: Partha Niyogi (University of Chicago), A Geometric Perspective on Learning theory and Algorithms.
May 11: Andrew Drucker (MIT), Improved Direct Product Theorems for Randomized Query Complexity.
May 18: Alex Samorodnitsky (Hebrew University and Radcliffe Institute), Maximal eigenvalues of subgraphs in the Hamming cube.
May 25: Yuan Zhou (Carnegie Mellon University and TTIC), Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT.
May 28, 2:30pm: Venkatesan Guruswami (Carnegie Mellon University), List Decodability of Random Linear Codes. Note non-standard day and time!
June 1: Vladimir Podolskii (Steklov Mathematical Institute), Bounds on Weights of Perceptrons.
June 3, 2:30pm: Ramamohan Paturi (University of California at San Diego), On the Complexity of Circuit Satisfiability. Note non-standard day and time!