CS6550/8803: Continuous Algorithms: Optimization and Sampling

Spring 2023. MW: 2-3:15pm, Weber SST III

Santosh Vempala, Klaus 2222.
TAs: Max Dabagia, Jai Moondra

The design of algorithms is traditionally a discrete endeavor. However, many advances have come from a continuous viewpoint. Typically, a continuous process, deterministic or randomized is designed (or shown) to have desirable properties, such as approaching an optimal solution or a desired distribution, and an algorithm is derived from this by appropriate discretization. We will use this viewpoint to develop several general techniques and build up to the state-of-the-art in polynomial algorithms for optimization and sampling.

Prerequisite: basic knowledge of algorithms, probability, linear algebra.


Textbook (in progress, with Yin Tat Lee)


Grading:
6550: One mid-term exam. Biweekly HW, including one longer HW towards the end. You are encouraged to collaborate on HW, but must write your own solutions. Submit via gradescope (link on canvas).
Send comments on lecture notes each week by email.
8803: Exam optional. Comment on lecture notes each week.
Bonus: suggesting simpler proofs, exercises, figures.