[Course description] [Announcements] [Lectures schedule] [Assignments] [Reading material]

**Instructor:** Robert
Krauthgamer

**When and where:** Wednesday, 4:15-6:00pm, Ziskind Lecture
Room 1

**First class: **March 12, 2014

**FGS code:** 20144182

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

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

**Previous offering:**
http://www.wisdom.weizmann.ac.il/~robi/teaching/2009b-SeminarGeometryAlgs

- [posted 2014-06-11]
**Additional class****on 2014-06-25**, at 10am in Pekeris room.

- [posted 2014-04-23]
**NO class on 2014-04-30** - [posted 2014-04-06] Corrected ex. 1 in problem set 1.

**NO class on 2014-03-19**

- 2014-03-12: Doubling dimension and Nearest Neighbor Search (to
be continued)

[homework: none] [reading: lecture notes #1]

2014-03-19: no class (faculty retreat)

- 2014-03-26: Doubling dimension and Nearest Neighbor Search
(continued)

[homework: problem set #1] [reading: lecture notes #2; papers KL04, BKL06, HM06, CG06] - 2014-04-02: Dimension reduction via random projections

[homework: none] [reading: Harvey, lecture #6; Goemans, lecture #6; my previous class, scribe #4] - 2014-04-09: Approximating MAX-CUT via Semidefinite Programming

[homework: problem set #2] [reading: Trevisan, lecture #7 (a guest lecture I gave); Williamson-Shmoys, Chapters 6.1-6.2]

- 2014-04-23: Polynomial Time Approximation Schemes for
Euclidean Traveling Salesman

[paper presented by Ami Mor + Dima Kogan] - 2014-05-07: Low-distortion embeddings and probabilistic
embedding into dominating trees

[homework: none] [reading: Fakcharoenphol-Rao-Talwar] - 2014-05-14: Probabilistic embedding into dominating trees
(cont'd)

[homework: problem set #3] [reading: Fakcharoenphol-Rao-Talwar]

- 2014-05-21: Approximating Multicut -- LP Rounding via Tree Embeddings;
- 2014-06-11: Turning big data into tiny data: Constant-size
coresets for k-means, PCA and projective clustering

[paper presented by Matan Karklinsky + Noam Arkind] - 2014-06-18: Near-Optimal Hashing Algorithms for Approximate
Nearest Neighbor in High Dimensions

[paper presented by Idan Himlich]

- 2014-06-25 (morning): Excluded minors, network decomposition,
and multicommodity flow

[paper presented by Lior Kamma] - 2014-06-25 (regular time): Planar Separators

[reading: lecture notes #12; Sommer, lecture #3]

2014-04-16: no class (Passover)

2014-04-30: no class (cancelled)

2014-05-28: no class (cancelled)

2014-06-04: no class (SHAVUOT)

- problem set 1 (posted March 27,
corrected April 6)

- problem set 2 (posted April 10)
- problem set 3 (posted May 15)

**Surveys and chapters:
**

- A revised and extended Chapter 15 of the book Lectures on Discrete Geometry by Jiri Matousek.
- A survey paper and talk from FOCS 2001 by Piotr Indyk.
- A chapter on embeddings by Piotr Indyk and Jiri Matousek, in Handbook of Discrete and Computational Geometry, CRC Press.
- A chapter on nesrest neighbor search by Piotr Indyk, in Handbook of Discrete and Computational Geometry, CRC Press.
- A survey on finite metric spaces by Nati Linial, in ICM 2002.

- Course on Algorithm design under a geometric lens by Anastasios Sidiropoulos at Ohio state, Spring 2014.
- Course
on Geometric Methods in Computer Science by Yair Bartal at
The Hebrew University, 2013.

- Course on metric embeddings by James R. Lee at U. Washington, Winter 2007.
- Course on metric embeddings by Michel Goemans at MIT, Fall 2006.
- Course on metric embeddings by Tim Roughgarden at Stanford, Winter 2006.
- Course on metric embeddings by Avner Magen at U. Toronto, Spring 2006.
- Course
on
measure concetration by Alexander
Barvinok at U. Michigan, Winter 2005.

- Course on metric embeddings by Harald Räcke at U. Chicago.
- Course on metric embeddings by Anupam Gupta and R. Ravi at CMU, Fall 2003.

Suggested papers for presentations (in crude categorization):

- [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 l
_{1}-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, Anastasios Sidiropoulos: Pathwidth, trees, and
random embeddings. Combinatorica 33(3): 349-374 (2013)

- [EE]
James R. Lee, Arnaud de Mesmay, Mohammad Moharrami: Dimension
Reduction for Finite Trees in ℓ 1. Discrete & Computational
Geometry 50(4): 977-1032 (2013)

- [EE] James R. Lee, Prasad Raghavendra: Coarse Differentiation and Multi-flows in Planar Graphs. Discrete & Computational Geometry 43(2): 346-362 (2010)
- Embedding a graph 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, Ofer Neiman: Using petal-decompositions to
build a low stretch spanning tree. STOC 2012: 395-406

- [EE] Rafail Ostrovsky, Yuval Rabani: Low distortion embeddings for edit distance. J. ACM 54(5): (2007)

- [EE] Sariel Har-Peled, Piotr Indyk, Rajeev Motwani: Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. Theory of Computing 8(1): 321-350 (2012)
- See also:

- [EE] Piotr Indyk, Rajeev Motwani: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998: 604-613
- [EE]
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)
- See also:

- [EE]
Ryan O'Donnell, Yi Wu, Yuan Zhou: Optimal lower bounds for
locality sensitive hashing (except when q is tiny). ICS 2011:
275-283

- [EE] Piotr Indyk: On Approximate Nearest
Neighbors under l
_{infinity}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
- [EE] Sariel Har-Peled, Nirman Kumar: Approximate Nearest Neighbor Search for Low-Dimensional Queries. SIAM J. Comput. 42(1): 138-159 (2013)
- [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.
- [EE] Piotr Indyk, Assaf Naor: Nearest-neighbor-preserving embeddings. ACM Transactions on Algorithms 3(3): (2007)
- (taken) [EE] Alexandr
Andoni, Piotr Indyk: Near-Optimal Hashing Algorithms for
Approximate Nearest Neighbor in High Dimensions. FOCS 2006:
459-468

Algorithms for processing metric spaces (including low-dimensional, doubling, or graphical):

- (taken) [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] Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. STOC 2012: 663-672
- [EE]
Yair Bartal, Lee-Ad Gottlieb: A Linear Time Approximation
Scheme for Euclidean TSP. FOCS 2013: 698-706

- [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)
- [EE] Sariel Har-Peled, Piotr Indyk, Anastasios Sidiropoulos: Euclidean spanners in high dimensions. SODA 2013: 804-809
- [EE]
Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi,
Venugopalan Ramasubramanian, Kunal Talwar: Reconstructing
approximate tree metrics. PODC 2007: 43-52

- [EE]
Claire Mathieu, Hang Zhou: Graph Reconstruction via Distance
Oracles. ICALP (1) 2013: 733-744

- [EE] Ittai Abraham, Amos Fiat, Andrew V. Goldberg, Renato Fonseca F. Werneck: Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. SODA 2010: 782-793
- [EE] Alexandr Andoni, Huy L. Nguyen: Near-Optimal Sublinear Time Algorithms for Ulam Distance. SODA 2010: 76-86
- [EE] Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, Christian Sohler: (1+ Є)-approximation for facility location in data streams. SODA 2013: 1710-1728
- (taken) [EE]
Dan Feldman, Melanie Schmidt, Christian Sohler: Turning big data
into tiny data: Constant-size coresets for k-means, PCA and
projective clustering. SODA 2013: 1434-1453

- [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 - [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] 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)
- [link] Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. SIAM J. Comput. 28(6): 2187-2214 (1999)
- (taken) [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]
James R. Lee, Manor Mendel, Mohammad Moharrami: A
node-capacitated Okamura-Seymour theorem. STOC 2013: 495-504

- [EE] Noga Alon, Assaf Naor: Approximating the Cut-Norm via Grothendieck's Inequality. SIAM J. Comput. 35(4): 787-803 (2006)
- [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