Yuval Rabani

 

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)