Seminar on Algorithms and Geometry (semester 2009B)

Instructor: Robert Krauthgamer

When and where: Thursdays 2-4pm, Ziskind 1

Students are asked to join the mailing list

Syllabus: This seminar will cover recent algorithmic topics that involve geometric concepts and techniques, including algorithms for nearest neighbor search, dimensionality reduction, metric embeddings, metric decompositions, and their applications to combinatorial algorithms such as approximation algorithms for graph partitioning.

The planned format is a combination of instructor lectures and student presentations, based on seminal papers and recent surveys.

Prerequisites: Basic knowledge of algorithms, at an undergraduate level, is required, and familiarity with Euclidean geometry, probability theory, and linear algebra may be necessary.


Announcements:


Schedule:
(weekly handouts typically include announcements, overview of topics covered, and problem sets)
 

Date

Topic

Reading

Handouts and scribes

Mar. 19

Embedding into l_infinity

[Matousek, chapter 15]

handout1, scribe1
Mar. 26
Low-distortion embeddings, sparsest-cut
[Matousek, chapter 15]
handout2, scribe2 
Apr. 2
Sparsest-cut (cont.) and min-bisection,
distortion lower bounds
[Matousek, chapter 15]
Vazirani/Approximation Algorithms
handout3, scribe3
Apr. 9
no class (holiday)


Apr. 16 Probabilistic embedding into trees
(Presenting: Noam+Liah)
[Fakcharoenphol-Rao-Talwar]
presentation1
Apr. 23  NNS in high dimensional spaces
(Presenting: Daniel+Mica)
[Indyk-Motwani]
handout4
presentation2
Apr. 30
no class (IMU meeting)


May 7
Dimension reduction in l_2
[Matousek, chapter 15], [Goemans, lecture 6], [Barvinok, section 3]
handout5, scribe4
May 14
Approximate distance oracles
(Presenting: Shiri)
[Thorup-Zwick]
presentation3
May 21
Measure concenctration on the sphere
[Matousek, chapters 14-15], [Goemans, lecture 6], [Barvinok, section 3] handout6, scribe5
May 28
no class (holiday)


June 4
Communication complexity of distance estimation
[Kushilevitz-Ostrosvky-Rabani]
handout7, scribe6
June 11
No dimension reduction in l_1

handout8
June 18
doubling metrics: Assouad's theorem and NNS
(taught by Lee-Ad Gottlieb)


June 25
Spectral partitioning in planar graphs
(Presenting: Yariv)
[Spielman-Teng]
presentation4, handout9

Note: Scribes are in somewhat draft form, and may skip details, have typos etc.
Scribes template: Use the example latex file sample-scribe.tex together with definitions file defs.tex; see the resulting sample-scribe.pdf


Relevant Resources:

Surveys and chapters:

Classes in other institutions:

Suggested papers for presentations (in crude categorization):

Low-distortion embeddings:
Nearest neighbor searching (NNS): Graph partitioning algorithms: