Here is the list of papers chosen for presentation by members of COMP670P

Note that the descriptions of the papers given come,  primarily,  from the bibliographies of other courses on the web.

Last updated 13/03/07

• Mordecai Golin

  • An introduction from Chapter 15 (latest version, 2005) of  Lectures on Discrete Geometry (Springer, May 2002) by Jiri Matousek

  • S. Dasgupta, A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures Algorithms, 2002.
        Chernoff-type proof of [JL84]

  • D. Achlioptas. Database Friendly Random Projections, PoDS 2000.
        How to do [JL84] with unbiased coins. 
     

• Sunil Arya

  • J. Kleinberg, Two Algorithms for Nearest-Neighbor Search in High Dimensions, STOC 1997.
        Random projection for near-neighbour searching.

  • P. Indyk, R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998.
        More approx NN searching; uses projections + "point location in equal balls"

  • . Kushilevitz and R. Ostrovsky and Y. Rabani. Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. STOC 1998.
        A form of dimension reduction for the hypercube, and using it for NN searching.
     

• Siu-Wing Cheng

  • S. Dasgupta, Learning Mixtures of Gaussians, FOCS 1999.
        Using dimension reduction for learning.

  • R. Arriaga, S. Vempala. An algorithmic theory of learning: robust concepts and random projection. FOCS 1999.
        Using dimension reduction for learning.
     

• Iris Reinbacher

  • A. Gupta, A. Kumar, R. Rastogi. Traveling with a Pez dispenser. FOCS 2001.
        Good tree covers for planar graphs, and using them for routing.

  • Y. Rabinovich, R. Raz. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. D&CG 99.
        Lower bounds on spanners. Shows: the n-cycle cannot be approximated by a tree.
     

• Yajun Wang

  • K. Dhamdhere, A. Gupta, and H. Raecke, Improved Embeddings of Graph Metrics into Random Trees, SODA '06.
        Probabilistic embedding of a graph into one of its spanning trees with maximum expected stretch O(log^2 n).

  • M. Elkin, Y. Emek, D. Spielman, and S. Teng, Lower-Stretch Spanning Trees, STOC '05.
        The big breakthrough (polylogarithmic maximum expected stretch) came in.
     

• Jian Xia

  • Gupta, Krauthgamer, Lee, Bounded geometries, fractals, and low-distortion embeddings, FOCS 2003.
    Tight bounds for embedding doubling metric into (low-dimensional) normed spaces.

  • Krauthgamer, Lee, Navigating nets: Simple algorithms for proximity search, SODA 2004.
    Present a simple deterministic data structure for maintaining a set S of points in a general metric space, 
    while supporting proximity search (nearest neighbor and range queries) and updates to S (insertions and
    deletions).
     

• Qin Zhang

  • U. Feige. Approximating the bandwidth via volume respecting embeddings. STOC 1998.
        How to maintain not only pair-wise distances, but also "volumes" of sets of points.
        Used for laying out graphs on the integers with small stretch (but arbitrary contraction).
       
  • M. Thorup, U.Zwick. Approximate distance oracles. STOC 2001.
        Gives tree covers: a small set of subtrees such that each shortest-path is maintained by one of them.
     

• Lee Chun Yu James

  • J. Fakcharoenphol, S. Rao and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003.
        A simple algorithm that gets the tight O(log n) result for all graphs.

  • M. Charikar, C. Chekuri, S. Guha, A. Goel, S. Plotkin. Approximating a Finite Metric by a Small Number of Tree Metrics. FOCS 98.
        How to derandomize Bartal's embeddings, via a "dual" problem.
     

• Zhang Yan

  • Sanjeev Arora, Satish Rao, Umesh Vazirani.
    Expander Flows, Geometric Embeddings, and Graph Partitionings
    STOC 2004: 36th Annual ACM Symposium on Theory of Computing, Pages 222-231.