# 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