Time
TuTh 3.305 in Center 208
Instructor:
Sanjoy Dasgupta
Office hours TBA in EBU3B 4138
This quarter the theme of CSE 254 is embeddings.
Prerequisite: CSE 202 and some background on probability (including
large deviation theory).
The first few lectures will consist of an overview of some basic material. Thereafter, in each class meeting, a student will give a talk lasting about 60 minutes presenting a recent technical paper in detail. In questions during the talk, and in the final 20 minutes, all seminar participants will discuss the paper and the issues raised by it.
Date  Presenter  
Jan 9  Sanjoy  Introduction 


Jan 11  Sanjoy  Some basics 


Jan 16  Sanjoy  Frechet and Bourgain embeddings  Matousek chapter 

Jan 18  no meeting  
Jan 23  Sanjoy  More on Bourgain  Matousek chapter  
Jan 25  Samory  JohnsonLindenstrauss lemma and lower bound  Dasgupta, Gupta; Matousek chapter  
Jan 30  no meeting: ITA conference  
Feb 1  no meeting: ITA conference  
Feb 6  Roy  Geometry of graphs, section 4: multicommodity flow  London, Linial, Rabinovich  notes 
Feb 8  Nakul  Nearestneighbor searching and metric space dimensions  Clarkson  slides 
Feb 13  Lawrence  Localitysensitive hashing based on pstable distributions  Datar, Immorlica, Indyk, Mirrokni  notes 
Feb 15  Konstantin  Nearest neighbor preserving embeddings  Indyk, Naor  notes 
Feb 20  Daniel  Approximating arbitrary metrics by tree metrics  Fakcharoenphol, Rao, Talwar  notes 
Feb 22  Fjola  Small distortion and volume preserving embeddings for planar and Euclidean metrics  Rao  slides 
Feb 27  Brian  Bounded geometries, fractals, and lowdistortion embeddings  Gupta, Krauthgamer, Lee  slides 
Mar 6  Evan  Measured descent  Krauthgamer, Lee, Mendel, Naor  slides 
Mar 8  Andy  Distance scales, embeddings, and metrics of negative type  Lee  slides 
Mar 13  Claire  Impossibility of dimension reduction in L1  Brinkman, Charikar  notes 
Mar 15  Neil  Euclidean spanners: short, thin, and lanky  Arya, Das, Mount, Salowe, Smid 
This is a four unit course in which the work consists of oral presentations.
The procedure for each student presentation is as follows:
The schedule of presentations will be determined as much as possible on Tuesday Jan 9. Here is a list of papers.
If you want to change your presentation date, please arrange a swap
with another student and notify me at least two weeks in advance.