Theory Seminar

Fall 2017 - CS 7890

*All seminars held in 122 Gates Hall at 4:00 pm unless otherwise noted*


Speaker :

Title :

Host :

August 28th, 2017 Laci Vegh, London School of Economics and Political Science A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
August 29th, 2017 Laci Vegh, London School of Economics and Political Science A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem NOTE: 4:15pm 253 Rhodes Hall*
September 4th, 2017 Labor Day No Theory Seminar  
September 11th, 2017 Yuval Peres, Microsoft Research, Redmond Trace reconstruction for the deletion channel Note: Joint talk with Probability Seminar. 4pm in Malott 406
September 18th, 2017 Vasilis Gkatzelis, Drexel University

Deferred-Acceptance Auctions: Worst-Case Approximation Guarantees 

September 25th, 2017 Gautam Kamath, MIT Statistical Hypothesis Testing in the Modern Age Jayadev Acharya
October 2nd, 2017 Nageeb Ali, Penn State A Theory of Self-Enforcing Coalitions Note: Joint talk with Microeconomic Theory Workshop. 4:15pm in 498 Uris Hall.
October 9th, 2017 Fall Break No Theory Seminar  
October 16th, 2017 Renato Paes Leme, Google Research New York Non-Clairvoyant Mechanism Design

*In Room 114 - The talk is based on joint work with Vahab Mirrokni, Pingzhong Tang and Song Zuo:

October 23rd, 2017 Richard Peng, Georgia Tech Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs This talk is based on,, and works in progress. They are joint with Michael B. Cohen, Jon Kelner, Rasmus Kyng, John Peebles, Anup B. Rao, Aaron Sidford, and Adrian Vladu.
October 30th, 2017 Alex Slivkins, Microsoft Research Bandits and agents: How to incentivize exploration?

Joint work with Yishay Mansour (Tel Aviv University and MSR Israel), Vasilis Syrgkanis (MSR-NE) and Steven Wu (MSR-NYC).

November 6th, 2017 Seb Bubeck, Microsoft Research

Kernel-based Methods for Bandit Convex Optimization

*In Room 114
November 13th, 2017 Luciano Pomatto, Caltech

Testable Forecasts

Note: Microeconomics Worksohp. 4:15pm in 498 Uris Hall
November 20th, 2017 Aleksander Madry, MIT

Gradient Descent: The Mother of All Algorithms?

November 27th, 2017 Scott Aaronson (UT Austin) Complexity - Theoretic Foundations of Quantum Supremacy Experiments *4p.m. - This is the Physics Colloquium. It will be held in Schwartz Auditorium in Rockefeller Hall.


To receive email announcements about the Theory Seminar, send name and email address to Vanessa Maley -

Details about student talks and reading group:



Spring 2017 | Fall 2016 Spring 2016 | Fall 2015 | Spring 2015 | Fall 2014 | Spring 2014 | Fall 2013 | Spring 2013 | Fall 2012 | Spring 2012 | Fall 2011 | Spring 2011 | Fall 2010
Spring 2010 | Fall 2009 | Spring 2009 | Fall 2008 | Spring 2008 | Fall 2007 | Spring 2007 | Fall 2006