Theory Seminar 2010 Academic Year
September 24, 3:30pm, Room 277: Yuri Gurevich (Microsoft Research), Linear Time Reasoning. Note non-standard day, time and place!
October 8, 2:30pm: Yevgeniy Dodis (New York University), Cryptography Against Continuous Memory Attacks. Note non-standard day and time!
October 19: Eric Allender (Rutgers University), Limits on the Computational Power of Random Strings.
October 26:
November 2: Pedro Felzenszwalb (University of Chicago), Fast Inference with Min-Sum Matrix Product (or how I finished a homework assignment 15 years later).
November 16: Arkadev Chattopadhyay (University of Toronto), Linear Systems over Arbitrary Moduli.
November 23: Ilya Safro (Argonne National Laboratory), Multilevel Algorithms for Large-Scale Combinatorial Optimization Problems.
November 30: Ankan Saha (University of Chicago), New Approximation Algorithms for Minimum Enclosing Shapes.
January 11: Aaron Potechin (MIT), Fourier Analysis and Invariants on Switching Networks for Directed Connectivity.
January 18: Yuri Makarychev (TTIC), Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability.
January 28, 4pm: Sourav Chakraborty (Chennai Institute for Mathematics), Nearly Tight Bounds for Testing Function Isomorphism. Note non-standard day and time!
February 9, 3:45pm: Balazs Szegedy (University of Toronto), Limits of Functions on Abelian Groups and Higher Order Fourier Analysis. Note non-standard day and time!
February 11, 10am, Room 277: Subhash Khot (New York University), A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. Note non-standard day, time and place!
February 22: YouMing Qiao (Tsinghua University), On isomorphism testing of groups with normal Hall subgroups.
March 8: Daniel Spielman (Yale University), Spectral Sparsification of Graphs and Approximations of Matrices.
March 29: Caroline Klivans (University of Chicago), Critical Groups. Re-scheduled from February 1.
April 5: Vijay Vazirani (Georgia Tech), Extending General Equilibrium Theory to the Digital Economy. Re-scheduled from November 9.
April 12: Gabor Kun (DIMACS and IAS), An Analytic Approach to the Dichotomy Conjecture.
April 19: Amir Shpilka (Technion and Microsoft Research), On the Minimal Fourier Degree of Symmetric Boolean Functions.
April 26, 10:30am, Ry 277: Varsha Dani , Scalable Mechanisms for Rational Secret Sharing. Note non-standard time and place!
April 26: Tom Hayes (University of New Mexico), Faster Liftings for Markov Chains.
May 3: Evgeny Dantsin (Roosevelt University), On the Certificate Complexity of Boolean Satisfiability.
May 10, 1:30pm, Room 276: Yevgeniy Dodis (New York University), Leftover Hash Lemma, Revisited. Note non-standard time and place!
May 17: Alexander Razborov (University of Chicago), Flag Algebras.
May 24: Mark Braverman (University of Toronto), Information and Interactive Communication.
July 8, 4:30pm, Ry 277: Martin Furer (Pennsylvania State University), How fast can we multiply?. Note non-standard day, time and place!