18.434: Seminar in Theoretical Computer Science
Spring 2014
This is an undergraduate seminar in theoretical computer science. It carries CIM credit for the math department. As with all CIM subjects, the emphasis is on communication, both oral and written. Enrollment is limited by the department. The topic for this Spring is geometry and polytopes. Geometric tools play a central role in modern algorithm design, and we will cover topics ranging from polytopes, measure concentration, metric embeddings, extended formulations, semi-definite programming, discrepancy theory, lattices and integer programming.
Please complete the course evaluation here, the deadline is 9am Monday May 19th.
Final Projects choose soon and discuss them with me! Resources: Annotated Paper, Advice
Homework #1 due in class April 2nd
Lecture Topics #2 in progress
Lecture Topics #1, references for what we already covered
If you have trouble with the material, talk to me before your presentation! Also I have added regular office hours (Mondays 3-4) in case you prefer to just drop by instead of setting up an appointment via email.
Course Information
- Instructor: Ankur Moitra
Office Hours: Monday 3-4 in E17-328
- Lecture: Mondays and Wednesdays 9:30-11:00, E17-129
- Note: Lorenzo Orecchia will be teaching another section of 18.434 which will focus on spectral graph theory. We will let students switch between these two classes in the first week, provided that they can find a student in the other class willing to switch with them.
- Text Book: We will follow some chapters from Lectures on Discrete Geometry by Jiri Matousek and A Course in Convexity by Alexander Barvinok. I will provide links to other references that we will use later in the class.
- Prerequisites: A course in algorithms at the level of 6.046
- Assessment: Students will be expected to give three lectures in class throughout the semester (40%) and a final projection (20%). Additionally, there will be a handful of problem sets (25%) and in-class participation (15%)
Course Outline
Here is a tentative outline for the course:
- Polytopes and Discrete Geometry
- Theorems of Radon, Caratheodory and Helly
- Separating Hyperplanes and Farkas' Lamma
- Linear Programming: Duality and Complementary Slackness
- Student Projects
- Birkhoff Polytope and Bipartite Matchings
- Spanning Tree Polytope
- Min-Cut Max-Flow via LP Duality
- Simplex Method: Pivoting and Termination
- Kalai-Kleitman Diameter Bound
- Matroids: Greedy Algorithm and Applications
- Semidefinite Programming
- Weak Duality and Strong Duality
- Ellipsoid Method
- Student Projects
- Hyperplane Rounding for MAXCUT and Correlation Clustering
- Perfect Graphs: Lovasz Theta Function and Applications
- Coloring 3-Colorable Graphs
- Conic Programming
- Grothendieck's Inequality and the Cut Norm
- Measure Concentration and Metric Embeddings
- Multicommodity Flow and Sparsest Cut
- Student Projects
- Metric Embeddings and Distortion
- Bourgain's Embedding Theorem
- Final Projects
- Measure Concentration
- Multiplicative Weights
- Earthmover Relaxation and Multiway Cut
- Metric Embeddings into Trees
- Lower Bounds for Metric Embeddings
- Oblivious Routing
- Weak Perfect Graph Theorem
- Iterative Rounding
- Minimizing Submodular Functions
- Maximum Volume Ellipsoids
Reference Material