Theory Seminar (Fall 2017)

If you are interested in giving a talk, email Shachar Lovett. For previous talks, please see the theory seminar archive.

Fall 2017

All talks are on Monday 2-3pm in Room CSE 4258 (Computer Science building, 4th floor), unless noted otherwise.

Eshan Chattopadhyay (Institute for Advanced Study)
Monday, October 2, 2017, 2:00pm
Towards Optimal Randomness Extractors and Ramsey Graphs

Shai Vardi (Caltech)
Monday, October 9, 2017, 2:00pm
Randomly coloring graphs of bounded treewidth

Monday, October 16, 2017, 2:00pm
No seminar (FOCS)

Swastik Kopparty (Rutgers)
Monday, October 23, 2017, 2:00pm
Recent results on locally testable codes and locally decodable codes

Clément Canonne (Columbia)
Monday, October 30, 2017, 2:00pm
When Fourier SIIRVs: Fourier-Based Testing for Families of Distributions

Nikhil Bansal (TU Eindhoven) 
Monday, November 6, 2017, 2:00pm
A fast polynomial space algorithm for Subset Sum

Thomas Rothvoss (University of Washington)
Monday, November 13, 2017, 2:00pm
The matching polytope has exponential extension complexity

Avishay Tal (Stanford)
Monday, November 20, 2017, 2:00pm
Computing Requires Larger Formulas than Approximating

Tselil Schramm (Berkeley)
Monday, November 27, 2017, 2:00pm
Spectral Algorithms Capture Sum-of-Squares on Average

Yin Tat Lee (University of Washington)
Monday, December 4, 2017, 2:00pm
KLS conjecture and log-Sobolev constant