TuTh 3.30-5 in Center 208
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.
|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:
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.