Yuval Rabani
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)