# 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 13:

October 20: Janos Simon (University of Chicago), Sorting by Random Insertion.

October 27:

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!