October 6: Toniann Pitassi (University of Toronto), Separating the analogs of NP, BPP and P in the NOF Multiparty Communication Model
October 13: Alexander Razborov (University of Chicago), A simple proof of Bazzi's theorem
October 23, 2:30pm: Prahladh Harsha (University of Texas at Austin), The Communication Complexity of Correlation
(notice non-standard day and time!)
October 30, 3:45pm (strict), Ryerson 358: Gil Kalai (Hebrew University and Yale University), Noise Sensitivity, Noise Stability, Percolation
and some connections to TCS
(notice non-standard day and room!)
November 3: Nathan Srebro (TTI-C), On the Informational Cost of Tractability
November 10: Ketan Mulmuley (University of Chicago), On P vs NP and Geometric Complexity Theory
(a joint meeting with the Logic Seminar: the talk begins at 2:30pm and will last for two hours)
November 17: Gyorgy Turan (University of Illinois at Chicago), Cube Partitions and Decision Trees
November 20: Yuri Makarychev (Microsoft Research), On the Advantage over Random for Maximum Acyclic Subgraph
(notice non-standard day!)
November 25, 12:30pm: Michael W. Mahoney (Stanford University), Statistical Leverage and Improved Matrix Algorithms
(notice non-standard day and time!)
December 1: James Lee (University of Washington), Eigenvalue Bounds, Spectral Partitioning,
and Flow Deformations
January 12: Nicole Immorlica (Northwestern University), The Role of Compatibility in Technology Diffusion on Social Networks
January 26:
Paolo Codenotti (University of Chicago), Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time
February 6, 2:30pm: Subhash Khot (New York University), Inapproximability of NP-complete problems, Discrete Fourier Analysis, and Geometry
(notice non-standard day and time!)
February 9: no seminar (TTI-C Workshop on Approximation Algorithms and their Limitations)
February 16:
Caroline Klivans (University of Chicago), Combinatorial Laplacians
February 23:
Dhruv Mubayi (University of Illinois at Chicago), Coloring Simple Hypergraphs
March 2: Lance Fortnow (Northwestern University), Program Equilibria and Discounted Computation Time
March 6, 2:30pm: Allan Borodin (University of Toronto), Sequential Elimination Graphs and Simple Combinatorial Algorithms
(notice non-standard day and time!)
March 30:
Raghav Kulkami (University of Chicago), Any Monotone Property of Sparse Graphs is Evasive
April 6:
Mark Braverman (Microsoft Research), Poly-logarithmic Independence Fools AC0 Circuits
April 13:
Hariharan Naranayan (University of Chicago), Random Walks on Polytopes and an Affine Interior Point Algorithm for Linear Programming
April 20:
Stephen Smale (TTI-C), Some Perspectives on Complexity Theory
April 27:
Zeev Dvir (IAS), Recent Progress on Kakeya Sets, Mergers and Extractors
May 4:
Ronen Basri (Weizmann Institute and TTI-C), Visibility Constraints on Features of 3D Objects
May 11: David Xiao (Princeton University), On the Black-box Complexity of PAC Learning
May 18:
Igor Pak (University of Minnesota), Combinatorics and Complexity of Partition Bijections
May 26, 3:00pm: Eli Ben-Sasson (Technion), Affine Dispersers from Subspace Polynomials
(notice non-standard day and time!)
June 1: no seminar (Workshop and Summer School on Theory and Practice of Computational Learning and 41st ACM Symposium on Theory of Computing)