Instructor: Brendan Juba

Tuesday/Thursday 11:30am-12:50pm, Cupples I 115

- Lasserre. Moments, positive polynomials, and their applications. Imperial College Press/World Scientific, 2010.
- Rothvoss 2013: MAPSP Tutorial: The Lasserre Hierarchy in Approximation Algorithms.
- Barak Steurer 2014: Sum-of-squares proofs and the quest towards optimal algorithms.
- Raghavendra Schramm Steurer 2017: High-dimensional estimation via sum-of-squares proofs.
- Fleming Kothari Pitassi 2019: Semialgebraic proofs and efficient algorithm design.

- 8/27: Moment problems; sum-of-squares relaxations, sum-of-squares proofs, and their relationship (Prof. Juba) notes
- 8/29: The use of sum-of-squares relaxations in optimization; standard bounds in sum-of-squares; overview of typical strategies for extracting solutions (Prof. Juba) notes
- 9/3-9/5: Hai S. Le and Zihao Deng - Juba AAAI 2019
- 9/10-9/12: Golnoosh Dehghanpoor - Barak Kelner Steurer STOC 2015
- 9/17-9/19: Aaron Handleman - Hopkins Steurer FOCS 2017 (conference version)
- 9/24-9/26: Sijia Wang - Ma Shi Steurer FOCS 2016 (conference version)
- 10/1: Alex Durgin - Hopkins Kothari Potechin Raghavendra Schramm Steurer FOCS 2017 (conference version) (10/3
*cancelled, rescheduled*) - 10/8-10/10: Ray Wu - Kothari Steinhardt Steurer STOC 2018 (full paper 1, full paper 2)
- 10/15-10/17: Fall Break/Aaron Handelman - Hopkins Steurer FOCS'17, concluded.
- 10/22-10/24: Andrew Estornell - Kothari Klivans Meka COLT 2018
- 10/29-10/31: Jizhou Huang - Karmalkar Kothari Klivans arXiv 2019/Raghavendra Yau arXiv 2019
- 11/5: Alex Durgin - Hopkins Kothari Potechin Raghavendra Schramm Steurer FOCS 2017, part 2.
- 11/7: Golnoosh Dehghanpoor - Object detection via sum-of-squares
- 11/12-11/14: No meeting (Prof. Juba traveling)
- 11/19-11/21: Andrew Estornell - Schramm Steurer COLT 2017
- 11/26-11/28: Thanksgiving break, no meeting
- 12/3-12/5: Hai S. Le - Combinatorial Bandits

- Barak Kelner Steurer STOC 2015 (GD)
- Ge Ma APPROX 2015
- Ma Shi Steurer FOCS 2016 (conference version) (SW)
- Bhattiprolu Guruswami Lee APPROX 2017

- Hopkins Steurer FOCS 2017 (conference version) (AH)
- Juba AAAI 2019 (HSL & ZD)

- Kothari Steinhardt Steurer STOC 2018 (full paper 1, full paper 2) (RW)
- Kothari Klivans Meka COLT 2018 (AE)
- Karmalkar Kothari Klivans arXiv 2019/Raghavendra Yau arXiv 2019 (JH)