Decompositions of Graphs and Their Applications

Spring Semester, 2008

This course deals with the following fundamental question: how does one partition a graph into several pieces? This question arises is various contexts, and the answers vary by the application in mind. We will discuss the desired properties of such a partition. We will design and analyze algorithms for computing a good partition. We will demonstrate applications in many areas: distributed computing, approximation algorithms, clustering and segmentation problems, routing in networks, geometric functional analysis.

This is a graduate level course aimed at students with a strong inclination towards theory. Students interested in networks, distributed systems, computer vision, data mining, and other areas, may as well find this course useful.

Prerequisites

Students are expected to possess reasonable mathematical skills, and to master basic concepts and techniques in the theory of algorithms, computational complexity, functional analysis, linear algebra, and probability theory.

Syllabus

Lecture 1: Properties and construction of graph decompositions.

Lecture 2: Sparse partitions, mobile user tracking.

Lecture 3: Region growing, flows and cuts.

Lecture 4: Construction of padded decompositions.

Lecture 5: Bi-Lipschitz maps via padded decompositions.

Lecture 6: HST approximations of metrics, metric labeling.

Lecture 7: Bourgain’s embedding, approximating expansion.

Lecture 8: Local versus global properties of metric spaces.

Lecture 9: 0-extension, lower bounds on Lipschitz maps.

Lecture 10: Measured descent.