CSE 254: Seminar on Learning Algorithms

Time
TuTh 3.30-5 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.

Discussion board


Date	Presenter	Paper	Author(s)	Slides
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:

One week in advance: Finish a draft of Latex/Powerpoint that present clearly the work in the paper. Make an appointment with me to discuss the draft slides. And email me the slides.
Several days in advance: Meet for about one hour to discuss improving the slides, and how to give a good presentation.
Day of presentation: Give a good presentation with confidence, enthusiasm, and clarity.
Less than three days afterwards: Make changes to the slides suggested by the class discussion, and email me the slides in PDF, two slides per page, for publishing. Try to make your PDF file less than one megabyte.

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.