CSE 254: Papers

Papers to be presented in class
Linial, London, and Rabinovich. The geometry of graphs and some of its algorithmic applications.
Brinkman and Charikar. On the impossibility of dimension reduction in Ll.
Fakcharoenphol, Rao, and Talwar. A tight bound on approximating arbitrary metrics by tree metrics.
Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics.
Newman and Rabinovich. A lower bound on the distortion of embedding planar metrics into Euclidean space.
Krauthgamer, Lee, Mendel and Naor. Measured descent: a new embedding method for finite metrics.
Gupta, Krauthgamer, Lee. Bounded geometries, fractals, and low-distortion embeddings.
Lee. Distance scales, embeddings, and metrics of negative type.
Arora, Lee, and Naor. Euclidean distortion and the sparsest cut.
Abraham, Bartal, Chan, Dhamdhere, Gupta, Neiman, and Kleinberg. Metric embeddings with relaxed guarantees.
Clarkson. Nearest-neighbor searching and metric space dimensions.
Datar, Immorlica, Indyk, and Mirrokni. Locality-sensitive hashing based on p-stable distributions.
Krauthgamer and Lee. Navigating nets: simple algorithms for proximity search.
Indyk and Naor. Nearest neighbor preserving embeddings.
Arya, Das, Mount, Salowe, and Smid. Euclidean spanners: short, thin, and lanky.
Sauer, Yorke, and Casdagli. Embedology.
Cutler. A review of the theory and estimation of fractal dimension.

Surveys and background reading
Indyk. Algorithmic applications of low-distortion embeddings.
Matousek, chapter 15 of the book Lectures on Discrete Geometry.
Scribe notes from a CMU course taught in Fall 2003 by Anupam Gupta and R. Ravi.