# 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 7: Konstantin Makarychev (Microsoft Research), Solving Optimization Problems with Diseconomies of Scale.

October 14: Ruta Mehta (Georgia Tech), Resolving The Complexity of Constant Rank Bimatrix Games.

November 4: Luca Trevisan (University of California at Berkeley), A Refined Cheeger Inequality and an Improved Analysis of Spectral Partitioning.

November 11: Edward Hirsch (Steklov Mathematical Institute at St. Petersburg), Distributional proving problems, and beyond.

November 18: Aaron Potechin (MIT), Sum of Squares Lower Bounds for the Planted Clique Problem.

November 25: Pooya Hatami (University of Chicago), A characterization of functions with vanishing averages over products of disjoint sets.

December 2: Tim Black (University of Chicago), Any Monotone k-Uniform Hypergraph Property is Weakly Evasive.

February 13, 10:30am, Ry255: James Lee (University of Washington), Lower bounds on the size of semidefinite programming relaxations. Note non-standard day, time and place

March 3: Ankur Moitra (MIT)