Geometric Methods in the Theory of Computation

Spring Semester, 2005

In this course we will discuss the relation between the geometry of finite metric spaces and the theory of algorithms and complexity theory. In particular, we will focus on applications in combinatorial optimization and in high dimensional computational geometry. We will survey geometric questions including bi-Lipschitz embeddings, dimension reduction, Lipschitz extensions, metric Ramsey theory, Isoperimetric inequalities, and Fourier analysis of Boolean functions.

This is a graduate level course aimed at students with a strong inclination towards theory.

Prerequisites

Students are expected to possess reasonable mathematical skills, and to master basic concepts and techniques in the theory of computation.

Lecture notes

Lecture 1: Introduction (.ps)

Lecture 2: Bourgain’s embedding theorem and its applications (.ps)

Lecture 3: Embedding lower bounds, Rao’s embedding theorem (.ps)

Lectures 4-6: Arora-Rao-Vazirani

Lecture 7: 0-Extension (.ps)

Lecture 8: Hierarchically separated trees (.ps)

Lecture 9: Dimension reduction

Lecture 10: The geometry of the binary cube, influence of variables (.ps)

Lecture 11: Influence upper bound, a counter-example to Borsuk’s conjecture (.ps)

Lecture 12: Coarse dimension reduction in the cube (.ps)