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.