# 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!