Seminar on Algorithms and Geometry (semester 2014B)

Weizmann Institute of Science

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

Course description

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.

Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2014b-SeminarGeometryAlgorithms

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

Announcements

[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

Lectures schedule

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-16: no class (Passover)

2014-04-23: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman
[paper presented by Ami Mor + Dima Kogan]

2014-04-30: no class (cancelled)

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-05-28: no class (cancelled)

2014-06-04: no class (SHAVUOT)

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]

Assignments

(Should be turned in within two weeks)

problem set 1 (posted March 27, corrected April 6)
problem set 2 (posted April 10)
problem set 3 (posted May 15)

Reading material

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.

Classes in other institutions:

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):

Low-distortion embeddings:

[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₁-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)

Nearest Neighbor Search (NNS):

[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

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

[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