Topics in theoretical computer science: an algorithmist's toolkit

Lectures: 2 sessions / week, 1.5 hours / session

This course will cover a collection of geometric techniques that apply broadly in modern algorithm design. The exact topics covered will depend on student interest, but a (perhaps overly ambitious) set of possibilities includes:

Graph Laplacians and their eigenvalues, connections to random walks and mixing, isoperimetric and Cheeger inequalities, expanders, and random graphs. Applications to include graph cutting, clustering, approximate counting, disjoint path problems, routing, and graph drawing.

Geometric properties of high-dimensional convex bodies, Fritz John's theorem and isotropy, Brunn-Minkowski and isoperimetric inequalities, concentration of measure and connections to probability theory. Applications to include volume computation and convex programming.

The multiplicative weights update method, its geometric meaning, and the many ways that it appears in modern computer science, with a focus on its use in optimization. Applications to include fast approximation algorithms for graph problems, "boosting" in learning and complexity theory, online algorithms, and zero-sum games.

How to use geometric information to quickly solve linear systems and eigenvalue problems. Will cover basic iterative methods, the Lanczos algorithm, conjugate gradients, preconditioning, and how spectral graph theory can be used to improve the construction of preconditioners.

Basic properties of lattices, Minkowski's theorem, and the LLL algorithm. Applications to include solving low-dimensional integer programs and breaking cryptosystems.

Linear and semidefinite programming relaxations of NP-hard problems, rounding techniques, and primal-dual methods.

The course requirements will comprise two parts:

I do not want this course to present an onerous workload, but I do want to give out enough problems to allow people to really learn the material. Since this is an advanced graduate class, I believe that students are capable of deciding for themselves how best to make this tradeoff. As such, I will hand out problem sets for each major topic and correct them, but I will not expect you to do all of the problems that I distribute. I will expect students to do as many as is necessary for a good-faith effort to learn the material. I recommend a total equivalent to at least two graduate problem sets over the course of the semester. Undergraduates taking this class will have a slightly more concrete set of requirements in which the number of required problems will be specified more precisely.

I would like to have scribes for every lectures. Each student should do his/her fair share of these.

Collaboration is encouraged on the problem sets. However, you should think about the problems yourself before discussing them with others. Furthermore, you must write your solutions up individually and understand anything that you hand in. If you do collaborate, you must acknowledge your collaborators in your writeup. Use of outside sources is strongly discouraged; if, however, you do use an outside source, you must reference it in your solution.

This is a graduate-level class and will move fairly quickly. We shall assume a significant level of mathematical maturity. The formal prerequisites are fairly minimal however; they consist of:

Some experience with algorithms beyond the introductory level will be helpful, but it is not strictly necessary.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare