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

Course Outline

Here is a tentative outline for the course:

Reference Material