**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**- The Multiplicative Weights Update Method: a Meta-Algorithm and Applications, by Arora, Hazan, Kale.
**interior point algorithms for maximum flow**- Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back, by Madry.
- Computing Maximum Flow with Augmenting Electrical Flows, by Madry.
**faster interior point and faster flow**- Path Finding I :Solving Linear Programs with O(sqrt(rank)) Linear System Solves, by Lee and Sidford.
- Path Finding II : An O(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem, by Lee and Sidford.
**faster cutting plane and combinatorial optimization**- A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization, by Lee, Sidford, Wong.
- Geometric Algorithms and Combinatorial Optimization, by Grotschel, Lovasz, Schrijver.
**Laplacian solvers and their applications**- Lx=b, by Vishnoi.
- Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple, by Kyng and Sachdeva.
**graph sparsification**- Spectral sparsification of graphs: theory and algorithms, by Batson, Spielman, Srivastava, Teng.
- Constructing linear-sized spectral sparsification in almost-linear time, by Lee and Sun.
**Brascramp-Lieb inequalities****discrepancy minimization**- An Algorithm for Komlos Conjecture Matching Banaszczyk's bound, by Bansal, Dadush, Garg.
- Constructive Discrepancy Minimization by Walking on The Edges, by Lovett and Meka.
**sampling in convex bodies**- Geometric Random Walks: A Survey, by Vempala.
**expansion in convex bodies**- Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion, by Lee and Vempala.
- Isoperimetric problems for convex bodies and a localization lemma, by Kannan, Lovasz, Simonovits.
**semidefinite programming and approximation algorithms**- Approximation Algorithms and Semidefinite Programming, by Gartner and Matousek.
**log-rank conjecture**- Communication is bounded by root of rank, by Lovett.
- A direct proof for Lovett's bound on the communication complexity of low rank matrices, by Rothvoss.
**maximizing determinant**- Randomized Rounding for the Largest Simplex Problem, by Nikolov.
- Maximizing Determinants under Partition Constraints, by Nikolov and Singh.
**interlacing families**- Ramanujan graphs and the solution of the Kadison-Singer problem, by Marcus, Spielman, Srivastava.