# Theory Seminar

Our seminar is intended to be broad and will (hopefully) cover not only what is traditionally referred to as "core theory", but also many topics at least distantly related to it. And when we are really interested in a result and/or a speaker, the employed notion of distance will be understood rather liberally!

Logistically, our normal meeting time and place is:

Tuesday, 3pm

Ryerson 251

(refreshments are served before the seminar). But, as a courtesy to our out-of-town speakers, we expect to meet occasionally on a different day, read the announcements carefully (and sign to our mailing list if you want to receive them on a regular basis).

## Current Year's Program

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 8: Jakob Nordstrom (Royal Institute of Technology, Stockholm), Narrow Proofs May Be Maximally Long. Note non-standard day

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