Seminar on Algorithms and Geometry (semester 2009B)
Instructor: Robert Krauthgamer
When and where: Thursdays 24pm, 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

Lowdistortion embeddings,
sparsestcut

[Matousek, chapter 15]

handout2,
scribe2

Apr. 2

Sparsestcut (cont.) and
minbisection,
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) 
[FakcharoenpholRaoTalwar]

presentation1

Apr. 23 
NNS in high dimensional spaces
(Presenting: Daniel+Mica) 
[IndykMotwani]

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)

[ThorupZwick]

presentation3

May 21

Measure concenctration on the
sphere

[Matousek, chapters 1415],
[Goemans, lecture 6], [Barvinok, section 3] 
handout6,
scribe5

May 28

no class
(holiday)



June 4

Communication complexity of
distance estimation

[KushilevitzOstrosvkyRabani]

handout7,
scribe6

June 11

No dimension reduction in l_1


handout8

June 18

doubling metrics: Assouad's
theorem and NNS
(taught by LeeAd Gottlieb)



June 25

Spectral partitioning in planar
graphs
(Presenting: Yariv)

[SpielmanTeng]

presentation4, handout9 
Note: Scribes are in
somewhat draft form, and may skip details, have typos etc.
Scribes template: Use
the example latex file samplescribe.tex
together with definitions file defs.tex;
see the resulting samplescribe.pdf
Relevant Resources:
Surveys and chapters:
Classes in other institutions:
Suggested papers for presentations (in crude categorization):
Lowdistortion 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): 485497 (2004)
 [link]
N. Linial, A. Magen, Assaf Naor: Girth and Euclidean Distortion,
Geometric and Functional Analysis (GAFA)12 (2002), no. 2, 380394
 [EE] Satish Rao:
Small Distortion and Volume Preserving Embeddings for Planar and
Euclidean Metrics.
Symposium on Computational Geometry 1999: 300306
 [EE] Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Cuts, Trees and l_{1}Embeddings of Graphs.
Combinatorica 24(2): 233269 (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: 9496
 [EE] Piotr Indyk,
Anastasios Sidiropoulos:
Probabilistic embeddings of bounded genus graphs into planar graphs.
Symposium on Computational Geometry 2007: 204209
 [EE]
James R. Lee,
Prasad Raghavendra:
Coarse Differentiation and Multiflows in Planar Graphs.
Electronic Colloquium on Computational Complexity (ECCC) 15(060): (2008)
 Embedding into spanning trees:
 [EE] Michael Elkin,
Yuval Emek,
Daniel A. Spielman,
ShangHua Teng:
LowerStretch Spanning Trees.
SIAM J. Comput. 38(2): 608628 (2008)
 [EE] Ittai Abraham,
Yair Bartal,
Ofer Neiman:
Nearly Tight Low Stretch Spanning Trees.
FOCS 2008: 781790
 [EE] Ittai Abraham,
Yair Bartal,
Ofer Neiman:
Embedding metric spaces in their intrinsic dimension.
SODA 2008: 363372
 [EE] Rafail Ostrovsky,
Yuval Rabani:
Low distortion embeddings for edit distance.
J. ACM 54(5): (2007)
Nearest neighbor searching (NNS):
 (taken) NNS
in highdimensional spaces:
 [EE]
Piotr Indyk,
Rajeev Motwani:
Approximate Nearest Neighbors: Towards Removing the Curse of
Dimensionality.
STOC 1998: 604613
 [link]
Eyal
Kushilevitz, Rafail
Ostrovsky,
Yuval Rabani:
Efficient Search for Approximate Nearest Neighbor in High Dimensional
Spaces. SIAM
J. Comput. 30(2): 457474 (2000)
 [EE]
Aristides Gionis,
Piotr Indyk,
Rajeev Motwani:
Similarity Search in High Dimensions via Hashing.
VLDB 1999: 518529
 [link]
Sariel HarPeled:
A Replacement for Voronoi Diagrams of Near Linear Size.
FOCS 2001: 94103
 [EE] Sanjoy Dasgupta,
Yoav Freund:
Random projection trees and low dimensional manifolds.
STOC 2008: 537546
 [EE]
Rajeev Motwani,
Assaf Naor,
Rina Panigrahy:
Lower Bounds on Locality Sensitive Hashing.
SIAM J. Discrete Math. 21(4): 930935 (2007)
 [EE] Piotr Indyk:
On Approximate Nearest Neighbors under l_{infinity} Norm.
J. Comput. Syst. Sci. 63(4): 627638 (2001)
 [EE] Piotr Indyk:
Approximate nearest neighbor algorithms for Frechet distance via
product metrics.
Symposium on Computational Geometry 2002: 102106
 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): 457474 (2000)
 [link]
T. S. Jayram, Ravi Kumar, D. Sivakumar: The OneWay Communication
Complexity of Hamming Distance. Theory of Computing, 4(1):129135,
2008
 [EE] Joshua
Brody, Amit Chakrabarti: A MultiRound Communication Lower Bound for
Gap Hamming and Some Consequences CoRR abs/0902.2399: (2009)
 Algorithms for metric spaces (including lowdimensional or
doubling):
 [EE]
Sanjeev Arora:
Polynomial Time Approximation Schemes for Euclidean Traveling Salesman
and other Geometric Problems.
J. ACM 45(5): 753782 (1998)
 See also: [EE] Kunal
Talwar:
Bypassing the embedding: algorithms for low dimensional metrics.
STOC 2004: 281290
 [EE]
Kenneth Clarkson: Nearestneighbor searching and metric space
dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors,
NearestNeighbor Methods for Learning and Vision: Theory and Practice,
pages 1559. MIT Press, 2006.
 (taken) [EE] Piotr
Indyk,
Assaf Naor:
Nearestneighborpreserving embeddings. ACM
Transactions on Algorithms 3(3): (2007)
 (taken) [EE] Mikkel Thorup,
Uri Zwick:
Approximate distance oracles.
J. ACM 52(1): 124 (2005)
 [EE] Mikkel Thorup:
Compact oracles for reachability and approximate distances in planar
digraphs.
J. ACM 51(6): 9931024 (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.
177189
 See also: [link]
Alon,
Noga;
Seymour, Paul; Thomas, Robin: Planar separators.
SIAM J. Discrete Math. 7 (1994), no. 2, 184193
 (taken) [link]
Daniel A. Spielman, ShangHua Teng: Spectral Partitioning Works: Planar
Graphs and Finite Element Meshes. FOCS 1996:96105
 [link] Alon,
Noga; Seymour, Paul; Thomas, Robin: A separator
theorem for nonplanar graphs. J. Amer. Math. Soc. 3
(1990), no. 4, 801808
 See also: [EE] Punyashloka
Biswal,
James R. Lee,
Satish Rao:
Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via
Flows.
FOCS 2008: 751760
 [link]
Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast
Approximate Graph Partitioning Algorithms. SIAM J. Comput. 28(6):
21872214 (1999)
 [EE] Noga Alon,
Assaf Naor:
Approximating the CutNorm via Grothendieck's Inequality.
SIAM J. Comput. 35(4): 787803 (2006)
 [link]
Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Approximate MaxFlow Min(Multi)Cut Theorems and Their Applications.
SIAM J. Comput. 25(2): 235251 (1996)
 [EE] Philip N. Klein,
Serge A. Plotkin,
Satish Rao:
Excluded minors, network decomposition, and multicommodity flow.
STOC 1993: 682690
 See also: [EE] Jittat Fakcharoenphol,
Kunal Talwar:
An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor.
RANDOMAPPROX 2003: 3646
 [EE] Uriel Feige,
MohammadTaghi Hajiaghayi,
James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators.
SIAM J. Comput. 38(2): 629657 (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): 616639 (2002)
 [EE] Harald Räcke:
Optimal hierarchical decompositions for congestion minimization in
networks.
STOC 2008: 255264