End of an intense week

End of the workshop on metric embeddings, algorithms and hardness of approximation. With hindsight, the title was a bit misleading. We have heard 2 talks on metric embeddings, and 20 talks on algorithms and hardness of approximation. But metric issues were present in many talks, with positive numbers attached to edges of a graph often interpreted as metrics, or output of an SDP interpreted as a metric embedding in Euclidean space.

I am glad that speakers have complied with the rule (gently enforced by Ryan O’Donnell, in charge of coordinating contents) that talks should be accessible to a wide audience. Nevertheless, I understand that computer scientists have suffered a bit under Valette, and mathematicians have found the rest of talks hard, especially those who missed the introductory courses by Mathieu, Périfel and Schabanel. I had skipped the complexity course, having benefitted from a working seminar organized by Périfel in University Paris 7, but followed Mathieu, and this has been an invaluable help.

All lectures have been filmed, the videos should be available on the web soon.

What comes next ? Courses again.

Some courses will be directly connected with the topics of the workshop. Kindler, Raghavendra and Regev will provide details of some of the results (inapproximability of MAX 3LIN, UGC-inapproximability of MAX CUT) that several speakers have alluded to. Lasserre will explain hierarchies, which were the subject of Georgiou’s talk. Cordero (completed by Ledoux) will discuss concentration, a tool which, among other things, is used to prove dimension reduction in Euclidean spaces (but this cannot work in l1, as Charikar explained). One aspect of Krauthgamer and Lee’s course, spectrum and decompositions of graphs, has already appeared in Steurer’s lectures. Mathieu proposes to go through the details of Arora, Barak and Steurer’s subexponential algorithm for Unique Games when she comes back in march.

Other courses will open doors to other subjects of common interest to mathematicians and computer scientists. Starting early next week, Linial will try a higher dimensional extension of Erdös’ theory of random graphs, Krauthgamer and Lee will uniformize graphs, i.e. construct optimal metrics on them.


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 http://www.math.ens.fr/metric2011/
This entry was posted in Announcement, Other and tagged . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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