Slides

• Lecture 1: Introduction
  


• Lecture 2: Nearest Neighbor in Euclidean norm (Johnson-Lindenstrauss Lemma, Locality Sensitive Hashing)
  


• Lecture 3: Nearest Neighbor in l_infty norm
  


• Lecture 4: Embeddings into l_infty (arbitrary metrics, Hausdorff metrics)
  


• Lecture 5: Algorithmic reductions to nearest neighbor (closest pair, diameter,MST,matching); revised 7/21/99
  


• Lecture 6: Sublinear time algorithms for general metrics (1-median, MAX-CUT, clustering)
  


• Conclusions and Open Problems

I also prepared a bibliography (with links to PS files, when possible) containing all references appearing in the above slides.