# Theory Seminar 2008 Academic Year

October 6, 2008: Toniann Pitassi (University of Toronto), Separating the analogs of NP, BPP and P in the NOF Multiparty Communication Model.

October 13, 2008: Alexander Razborov (University of Chicago), A simple proof of Bazzi's theorem.

October 23, 2008, 2:30pm: Prahladh Harsha (University of Texas at Austin), The Communication Complexity of Correlation. Note non-standard day and time!

October 30, 2008, 3:45 (Ryerson 358): Gil Kalai (Hebrew University and Yale University), Noise Sensitivity, Noise Stability, Percolation and some connections to TCS. Note non-standard day and room!

November 3, 2008: Nathan Srebro (TTI-C), On the Informational Cost of Tractability.

November 10, 2008: Ketan Mulmuley (University of Chicago), On P vs NP and Geometric Complexity Theory. This is a joint meeting with the Logic Seminar: the talk begins at 2:30pm and will last for two hours.

November 17, 2008: Gyorgy Turan (University of Illinois at Chicago), Cube Partitions and Decision Trees.

November 20, 2008: Yuri Makarychev (Microsoft Research), On the Advantage over Random for Maximum Acyclic Subgraph. Note non-standard day!

November 25, 2008, 12:30pm: Michael W. Mahoney (Stanford University), Statistical Leverage and Improved Matrix Algorithms. Note non-standard day and time!

December 1, 2008: James Lee (University of Washington), Eigenvalue Bounds, Spectral Partitioning, and Flow Deformations.

January 9, 2009, 2:30pm: Scott Aaronson (MIT), The Limits of Advice. Note non-standard day and time!

January 12, 2009: Nicole Immorlica (Northwestern University), The Role of Compatibility in Technology Diffusion on Social Networks.

January 19, 2009:

January 26, 2009: Paolo Codenotti (University of Chicago), Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time.

February 6, 2009 2:30pm: Subhash Khot (New York University), Inapproximability of NP-complete problems, Discrete Fourier Analysis, and Geometry.

February 9, 2009:

February 16, 2009: Caroline Klivans (University of Chicago), Combinatorial Laplacians.

February 23, 2009: Dhruv Mubayi (University of Illinois at Chicago), Coloring Simple Hypergraphs.

March 2, 2009: Lance Fortnow (Northwestern University), Program Equilibria and Discounted Computation Time.

March 6, 2009, 2:30pm: Allan Borodin (University of Toronto), Sequential Elimination Graphs and Simple Combinatorial Algorithms. Note non-standard day and time!

March 30, 2009: Raghav Kulkami (University of Chicago), Any Monotone Property of Sparse Graphs is Evasive.

April 6, 2009: Mark Braverman (Microsoft Research), Poly-logarithmic Independence Fools AC0 Circuits.

April 13, 2009: Hariharan Naranayan (University of Chicago), Random Walks on Polytopes and an Affine Interior Point Algorithm for Linear Programming.

April 20, 2009: Stephen Smale (TTI-C), Some Perspectives on Complexity Theory.

April 27, 2009: Zeev Dvir (IAS), Recent Progress on Kakeya Sets, Mergers and Extractors.

May 4, 2009: Ronen Basri (Weizmann Institute and TTI-C), Visibility Constraints on Features of 3D Objects.

May 11, 2009: David Xiao (Princeton University), On the Black-box Complexity of PAC Learning.

May 18, 2009: Igor Pak (University of Minnesota), Combinatorics and Complexity of Partition Bijections.

May 26, 2009, 3:00pm: Eli Ben-Sasson (Technion), Affine Dispersers from Subspace Polynomials. Note non-standard day and time!

June 1, 2009: