CSE 254: Seminar on Learning Algorithms

TuTh 3.30-5 in Center 208

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.

Discussion board

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 Johnson-Lindenstrauss 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 Nearest-neighbor searching and metric space dimensions Clarkson slides
Feb 13 Lawrence Locality-sensitive hashing based on p-stable 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 low-distortion 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:

Please read, reflect upon, and follow these presentation guidelines, courtesy of Prof Charles Elkan.  Presentations will be evaluated, in a friendly way but with high standards, using this feedback form.

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.