Course projects
There will be a course project which contributes 50% to the course grade.
The purpose is to acquire a deeper understanding on a specific topic/technique of your own interest.
You are encouraged to pick any convexity related topic close to your own research interests.
The basic requirement is to read papers and write a survey, of course you are most welcome to do original research.
Below are some project ideas, mostly further references to topics relevant to the course.
- gradient descent for approximate max-flow min-cut
- A new approach to computing maximum flows using electrical flows, by Lee, Rao, Srivastava.
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs, by Christiano, Kelner, Madry, Spielman, Teng.
- multiplicative weight update method
- interior point algorithms for maximum flow
- faster interior point and faster flow
- faster cutting plane and combinatorial optimization
- Laplacian solvers and their applications
- graph sparsification
- Brascramp-Lieb inequalities
- discrepancy minimization
- sampling in convex bodies
- expansion in convex bodies
- semidefinite programming and approximation algorithms
- log-rank conjecture
- maximizing determinant
- interlacing families