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:
- Posted April 6: There is
a correction to Problem 3 in Handout 2. Download the new version below.
- Posted Mar. 19: Next two classes (Mar. 26 and Apr. 2) will start
20 minutes early
- Posted Mar. 19: There will be no class on April 30, due to
a meeting of the Israel Math Union
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:
- (taken) [EE] Jittat Fakcharoenphol,
Satish Rao,
Kunal Talwar:
A tight bound on approximating arbitrary metrics by tree metrics.
J. Comput. Syst. Sci. 69(3): 485-497 (2004)
- [link]
N. Linial, A. Magen, Assaf Naor: Girth and Euclidean Distortion,
Geometric and Functional Analysis (GAFA)12 (2002), no. 2, 380-394
- [EE] Satish Rao:
Small Distortion and Volume Preserving Embeddings for Planar and
Euclidean Metrics.
Symposium on Computational Geometry 1999: 300-306
- [EE] Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs.
Combinatorica 24(2): 233-269 (2004)
- See also: [EE] Ilan Newman,
Yuri Rabinovich:
A lower bound on the distortion of embedding planar metrics into
Euclidean space.
Symposium on Computational Geometry 2002: 94-96
- [EE] Piotr Indyk,
Anastasios Sidiropoulos:
Probabilistic embeddings of bounded genus graphs into planar graphs.
Symposium on Computational Geometry 2007: 204-209
- [EE]
James R. Lee,
Prasad Raghavendra:
Coarse Differentiation and Multi-flows in Planar Graphs.
Electronic Colloquium on Computational Complexity (ECCC) 15(060): (2008)
- Embedding into spanning trees:
- [EE] Michael Elkin,
Yuval Emek,
Daniel A. Spielman,
Shang-Hua Teng:
Lower-Stretch Spanning Trees.
SIAM J. Comput. 38(2): 608-628 (2008)
- [EE] Ittai Abraham,
Yair Bartal,
Ofer Neiman:
Nearly Tight Low Stretch Spanning Trees.
FOCS 2008: 781-790
- [EE] Ittai Abraham,
Yair Bartal,
Ofer Neiman:
Embedding metric spaces in their intrinsic dimension.
SODA 2008: 363-372
- [EE] Rafail Ostrovsky,
Yuval Rabani:
Low distortion embeddings for edit distance.
J. ACM 54(5): (2007)
Nearest neighbor searching (NNS):
- (taken) NNS
in high-dimensional spaces:
- [EE]
Piotr Indyk,
Rajeev Motwani:
Approximate Nearest Neighbors: Towards Removing the Curse of
Dimensionality.
STOC 1998: 604-613
- [link]
Eyal
Kushilevitz, Rafail
Ostrovsky,
Yuval Rabani:
Efficient Search for Approximate Nearest Neighbor in High Dimensional
Spaces. SIAM
J. Comput. 30(2): 457-474 (2000)
- [EE]
Aristides Gionis,
Piotr Indyk,
Rajeev Motwani:
Similarity Search in High Dimensions via Hashing.
VLDB 1999: 518-529
- [link]
Sariel Har-Peled:
A Replacement for Voronoi Diagrams of Near Linear Size.
FOCS 2001: 94-103
- [EE] Sanjoy Dasgupta,
Yoav Freund:
Random projection trees and low dimensional manifolds.
STOC 2008: 537-546
- [EE]
Rajeev Motwani,
Assaf Naor,
Rina Panigrahy:
Lower Bounds on Locality Sensitive Hashing.
SIAM J. Discrete Math. 21(4): 930-935 (2007)
- [EE] Piotr Indyk:
On Approximate Nearest Neighbors under linfinity Norm.
J. Comput. Syst. Sci. 63(4): 627-638 (2001)
- [EE] Piotr Indyk:
Approximate nearest neighbor algorithms for Frechet distance via
product metrics.
Symposium on Computational Geometry 2002: 102-106
- Communication complexity of Hamming distance, upper and lower
bounds from:
- [link]
Eyal
Kushilevitz, Rafail
Ostrovsky,
Yuval Rabani:
Efficient Search for Approximate Nearest Neighbor in High Dimensional
Spaces. SIAM
J. Comput. 30(2): 457-474 (2000)
- [link]
T. S. Jayram, Ravi Kumar, D. Sivakumar: The One-Way Communication
Complexity of Hamming Distance. Theory of Computing, 4(1):129-135,
2008
- [EE] Joshua
Brody, Amit Chakrabarti: A Multi-Round Communication Lower Bound for
Gap Hamming and Some Consequences CoRR abs/0902.2399: (2009)
Algorithms for metric spaces (including low-dimensional or
doubling):
- [EE]
Sanjeev Arora:
Polynomial Time Approximation Schemes for Euclidean Traveling Salesman
and other Geometric Problems.
J. ACM 45(5): 753-782 (1998)
- See also: [EE] Kunal
Talwar:
Bypassing the embedding: algorithms for low dimensional metrics.
STOC 2004: 281-290
- [EE]
Kenneth Clarkson: Nearest-neighbor searching and metric space
dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors,
Nearest-Neighbor Methods for Learning and Vision: Theory and Practice,
pages 15-59. MIT Press, 2006.
- (taken) [EE] Piotr
Indyk,
Assaf Naor:
Nearest-neighbor-preserving embeddings. ACM
Transactions on Algorithms 3(3): (2007)
- (taken) [EE] Mikkel Thorup,
Uri Zwick:
Approximate distance oracles.
J. ACM 52(1): 1-24 (2005)
- [EE] Mikkel Thorup:
Compact oracles for reachability and approximate distances in planar
digraphs.
J. ACM 51(6): 993-1024 (2004)
Graph partitioning algorithms:
- [link, link2] Richard J.
Lipton and Robert Endre Tarjan: A Separator Theorem for Planar Graphs.
SIAM Journal on Applied Mathematics, Vol. 36, No. 2 (Apr., 1979), pp.
177-189
- See also: [link]
Alon,
Noga;
Seymour, Paul; Thomas, Robin: Planar separators.
SIAM J. Discrete Math. 7 (1994), no. 2, 184--193
- (taken) [link]
Daniel A. Spielman, Shang-Hua Teng: Spectral Partitioning Works: Planar
Graphs and Finite Element Meshes. FOCS 1996:96-105
- [link] Alon,
Noga; Seymour, Paul; Thomas, Robin: A separator
theorem for nonplanar graphs. J. Amer. Math. Soc. 3
(1990), no. 4, 801--808
- See also: [EE] Punyashloka
Biswal,
James R. Lee,
Satish Rao:
Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via
Flows.
FOCS 2008: 751-760
- [link]
Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast
Approximate Graph Partitioning Algorithms. SIAM J. Comput. 28(6):
2187-2214 (1999)
- [EE] Noga Alon,
Assaf Naor:
Approximating the Cut-Norm via Grothendieck's Inequality.
SIAM J. Comput. 35(4): 787-803 (2006)
- [link]
Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.
SIAM J. Comput. 25(2): 235-251 (1996)
- [EE] Philip N. Klein,
Serge A. Plotkin,
Satish Rao:
Excluded minors, network decomposition, and multicommodity flow.
STOC 1993: 682-690
- See also: [EE] Jittat Fakcharoenphol,
Kunal Talwar:
An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor.
RANDOM-APPROX 2003: 36-46
- [EE] Uriel Feige,
MohammadTaghi Hajiaghayi,
James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators.
SIAM J. Comput. 38(2): 629-657 (2008)
- [EE] Jon
M.
Kleinberg,
Éva Tardos:
Approximation algorithms for classification problems with pairwise
relationships: metric labeling and Markov random fields.
J. ACM 49(5): 616-639 (2002)
- [EE] Harald Räcke:
Optimal hierarchical decompositions for congestion minimization in
networks.
STOC 2008: 255-264