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: