Theory Seminar 2013 Academic Year
October 1: Travis Johnston (Universtiy of South Carolina), Connecting Turan Problems on Hypergraphs to Forbidden Subposet Problems.
October 7, 2:30pm: Yuri Gurevich (Microsoft Research), Semantics-to-syntax analyses of algorithms. Note non-standard time and day
October 8: Ravi Kannan (Microsoft Research India), Nimble Algorithms for Cloud Computing. Joint meeting with the Scientific and Statistical Computing Seminar
October 15: John Wilmes (University of Chicago), Faster Canonical Forms for Strongly Regular Graphs.
October 22: Benjamin Rossman (National Institute of Informatics, Tokyo), Formulas vs. Circuits for Small Distance Connectivity.
November 19: Shachar Lovett (University of California at San Diego), Communication is bounded by root of rank.
November 26: Daniel Reichman (Weizmann Institute), The layers model and applications.
December 10: Nikhil Srivastava (Microsoft Research Bangalore), Bipartite Ramanujan Graphs of Every Degree.
January 28: Nina Balcan (Georgia Tech), Learning Valuation Functions.
February 4: Klim Efremenko (University of Chicago), List and Unique Coding of Interactive Communication.
March 5, 3:30pm: Leonid Gurvits (City College of New York), Breaking $e^n$ Barrier for Deterministic Poly-Time Approximation of the Permanent and Settling Friedland’s Conjecture on the Monomer-Dimer Entropy. Joint meeting with the Scientific and Statistical Computing Seminar. Note non-standard day and time
March 7, 1:30pm, Eckhart 133: Assaf Naor (Courant Institute), Vertical versus horizontal Poincare inequalities. Joint meeting with the Math Colloquium. Note non-standard day, time and place
March 18, Ry 276: Anindya De (IAS), Central limit theorem for Gaussian chaos, Polynomial decomposition and deterministic approximate counting for low-degree polynomial threshold functions. Note non-standard room
March 24, 11am: Andrew Drucker (IAS), Confident Predictions Against an Adversary. Note non-standard day and time
April 1: Konstantin Makarychev (Microsoft Research), Constant Factor Approximation for Balanced Cut in the PIE Model.
April 2, 4:30pm: Jin-Yi Cai (University of Wisconsin - Madison), Siegel's Theorem, Edge Coloring, and a Holant Dichotomy. Joint meeting with the Algebraic Geometry Seminar. Note non-standard day and time
April 29: Yaoyun Shi (University of Michigan), True Randomness: Its Origin and Expansion.
May 6: Nicholas Harvey (University of British Columbia), Spectrally Thin Trees.
May 9, 10:30am, Ry277: Jakob Nordstrom (Royal Institute of Technology, Stockholm), Narrow Proofs May Be Maximally Long. Note non-standard day, time and room
May 13: Shengyu Zhang (Chinese University of Hong Kong), Fourier sparsity, spectral norm, and the Log-rank conjecture.
May 30: Aleksander Madry (Ecole Polytechnique Federale De Lausanne), Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back. Note non-standard day