Next week’s workshop

The schedule of next week’s workshop has been finalized tonight. Two mini-courses will start on monday (O’Donnell in the morning, Dinur in the afternoon). Sanjeev Arora’s minicourse will start on tuesday. This will be a two-voices course, since David Steurer will second Sanjeev at the end of the week.

Here is a comment on Moses Charikar’s talk, scheduled on monday. It has to do with dimension reduction, a subject that has been treated this week in Cambridge by Yuval Rabani (hopefully, Yuval will show up in Paris for the march workshop). Several classical algorithms use, as an intermediate step, an embedding of a graph in a Banach space. In can be Euclidean space, or L1.

For instance, the Goemans-Williamson algorithm for MAX CUT (see Claire Mathieu’s first lecture) uses an SDP which produces an embedding of the graph in a possibly high dimensional Euclidean space. The rounding procedure involves the random choice of a hyperplane in that space. One possible way to derandomize the algorithm consists in first reducing dimension by projecting orthogonally onto a subspace of much smaller dimension, and then applying the conditional expectation method.

It is a theorem of Johnson and Lindenstrauss which allows to reduce dimension. They observed that given a finite set of points in Euclidean space, there exists an orthogonal projection onto a low dimensional subspace which negligibly distorts distances in the finite set. They use the probabilistic method : a random projection does well, this follows easily from the concentration of measure phenomenon.

Embeddings in L1 arise in a famous LP-based algorithm for solving SPARSEST CUT, devised by Linial, London and Rabinovitch. The embedding is produced by Bourgain’s embedding theorem for finite metric spaces. It is tempting to look for nearly L1-distance preserving projections, but unfortunately, such things do not exist. This was observed by Brinkman and Charikar a few years ago, and Moses Charikar will discuss this and recent improvements on.

Dimension reduction in Loo does not work well either (Matousek).


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Announcement, Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s