**CS 798: Convexity and Optimization**

Lecture: | Wednesdays and Fridays, 10:30-11:50, DC 2568. |
---|---|

Instructor: | Lap Chi Lau |

Office hours: | Fridays, 2-3, DC 3120. |

Tutor: | Tsz Chiu Kwok |

Piazza: | piazza.com/uwaterloo.ca/winter2017/cs798a |

In this course, we will study some recent developments in theoretical computer science using tools from convex optimization and convex geometry. Towards this goal, we will cover the fundamentals required in these areas. The following is a tentative syllabus.

- convex sets, convex functions, examples, inequalities.
- duality, separating hyperplane, optimality conditions, John ellipsoid.
- gradient descent algorithms, approximating min-cut.
- multiplicative update, mirror descent, approximate Caratheodory.
- Newton method, interior point method, maximum flow.
- ellipsoid method, cutting plane method, matroid intersection, geometric descent.
- volume, Brunn-Minkowski's inequality, Grunbaum's theorem.
- isoperimetric inequalities, concentration of measure, discrepancy minimization.
- random sampling in convex bodies.
- semidefinite programming, Grothendieck's inequality, log-rank conjecture.

**References:** Notes will be provided.
The following is a list of primary references.

- Convex Optimization, by Boyd and Vandenberghe.
- Convex Optimization: Algorithms and Complexity, by Bubeck.
- An Elementary Introduction to Modern Convex Geometry, by Ball.
- Algorithmic Convex Geometry, by Vempala.