********************************************************* DIMACS Workshop on Discrete Metric Spaces and their Algorithmic Applications August 20 - 23, 2003 Princeton University, Princeton, New Jersey ORGANIZERS Moses Charikar Princeton University moses at CS.Princeton.EDU Piotr Indyk MIT indyk at theory.lcs.mit.edu Nati Linial Hebrew University nati at cs.huji.ac.il Jiri Matousek Charles University matousek at kam.mff.cuni.cz Yuri Rabinovich University of Haifa yuri at cs.haifa.ac.il Gideon Schechtman Weizmann Institute gideon at wisdom.weizmann.ac.il Co-sponsored by the Institute for Advanced Study and Princeton University. Presented under the auspices of the DIMACS Special Focus on Data Analysis and Mining ********************************************************************* The study of finite metric spaces and metric embeddings has its origins in Banach space theory and functional analysis. In recent years, this area has emerged as a new and influentual branch of discrete mathematics, with deep and surprising applications in Computer Science. Theoretical computer scientists are now familiar with the work of Bourgain, who showed that any metric on n points can be embedded with O(log n) distortion in Euclidean space, as well as the fundamental dimension reduction result of Johnson and Lindenstrauss who showed that any n points in Euclidean space can be embedded in O(log(n)/ e 2 ) dimensions with a (1 + e )-distortion in distances. Following the work of Linial, London and Rabinovich, Bourgain's result has found novel applications to approximation algorithms. The Johnson Lindenstrauss lemma has been used as a basic tool for dealing with high dimensional data. It has also been used extensively in the design of algorithms and data structures for various problems in high dimensional computational geometry. There has been a lot of interest and activity in this area in the past few years. New insights into metric embeddings have been developed as well as new applications and connections discovered to approximation algorithms, algorithms for large data sets, and algorithms for high dimensional computational geometry. In the last two years, there have been several surveys on the subject. Piotr Indyk gave a tutorial at FOCS 2001 on algorithmic applications of low distortion embeddings. Jiri Matousek wrote a chapter on mathematical aspects of embeddings in his recent book on discrete geometry. Nati Linial gave a survey on finite metric spaces and their connec-tion to combinatorics, geometry and algorithms at the International Congress of Mathematicians last year. Also, Piotr Indyk and Jiri Matousek recently wrote a chapter on low distortion embeddings of finite metric spaces for the upcoming Handbook of Discrete and Computational Geometry. Last year, a workshop on discrete metric spaces was held at Haifa, March 3-7, 2002 and was quite successful (http://cs.haifa.ac.il/~yuri/DMSA02.html). Besides bringing together researchers in the area and facilitating research and discussion, one of the achievements of the workshop was to compile a list of open problems in the field, (http://kam.mff.cuni.cz/~matousek/haifaop.ps). The large list of intriguing open problems is a good indication of the vitality of this area. Also interesting to note is the fact that since that list was compiled, 5 open questions on that list have been resolved (as of Jan 27, 2003). Given the furious pace of new developments in this area, we plan to organize a followup work-shop in Princeton this summer. In particular, we would like to take advantage of the following opportunity: the RANDOM and APPROX conferences will be held in Princeton Aug 24-26, 2003. We intend to have our workshop just before the conference and take advantage of the fact that there is a significant overlap between the target audience of the workshop and that of RANDOM-APPROX. Also, we expect that several interested US participants who could not take advantage of the Haifa workshop last year will find it easier to attend the workshop in Princeton. The questions in this field are a beautiful blend of combinatorics and geometry with several con-nections to algorithm design and analysis. Here are some of the topics that the proposed workshop will cover: * Embeddings in normed spaces and connections to Banach space theory. * Embeddings of planar graphs, low distortion embeddings into trees and their applications to approximation algorithms. * Metric Ramsey type theorems. * Low dimensional embeddings and connections to algorithmic techniques for large data sets. * Embeddings of special metrics (e.g. edit distance, frechet distance, etc.) and applications to high dimensional computational geometry. * Graph representations, distance labelings, graph spanners, etc. ********************************************************************** Call for Participation: The workshop will consist of invited presentations of researchers working in the field of embeddings and related areas of mathematics and computer science. A preliminary list of invited speakers and participants is attached below. In addition, the workshop will feature several tutorials on embeddings as well as their algorithmic applications. A partial list of tutorials includes: * - "Embeddings and computation over streaming data" (S. Muthukrishnan) * - "Embeddings and approximation algorithms for NP-hard problems" (R. Ravi) * - "Lipschitz quotient maps between Banach spaces" (Bill Johnson) Preliminary list of invited speakers and participants: Dimitris Achlioptas, Microsoft Mihai Badoiu, MIT Yair Bartal, Hebrew University Bo Brinkman, Princeton University Jeremy Buhler, Washington University Bernard Chazelle, Princeton University Chandra Chekuri, Bell Labs Victor Chepoi, Universite de la Mediterranee, Marseille Graham Cormode, DIMACS Michel Deza, Ecole Normale Superieure Kedar Dhamdhere, CMU Michael Elkin, IAS Princeton Martin Farach-Colton, Rutgers University Sudipto Guha, University of Pennsylvania Anupam Gupta, CMU Bill Johnson, Texas A&M Nigel Kalton, University of Missouri Ravi Kumar, IBM Almaden Robert Krauthgamer, University of California, Berkeley James R. Lee, University of California, Berkeley Joram Lindenstrauss, Hebrew University Avner Magen, University of Toronto S. Muthukrishnan, Rutgers University Assaf Naor, Microsoft Seffi Naor, Technion Ilan Newman, Haifa University Yuval Rabani, Technion R. Ravi, CMU Amit Sahai, Princeton University Cenk Sahinalp, CWRU Stephen Semmes, Rice University Martin Strauss, AT&T Labs Kunal Talwar, University of California, Berkeley Santosh Vempala MIT Avi Wigderson, IAS Princeton David Woodruff, MIT ******************************************************** Workshop Program: Wednesday, August 20, 2003 8:30 - 9:00 Breakfast and registration 9:00 - 9:30 Introduction Jiri Matousek 9:30 - 11:00 Tutorial: Embeddings and approximation algorithms for NP-hard problems Ramamoorthi Ravi 11:00 - 11:15 Break 11:15 - 12:00 Approximating arbitrary metrics by tree metrics Kunal Talwar 12:00 - 1:30 Lunch 1:30 - 2:15 (Nearly) Optimal Embeddings into Additive and Ultrametric Trees Martin Farach-Colton 2:15 - 3:00 Approximating minimum average distortion of non-contracting embeddings Kedar Dhamdhere 3:30 - 4:15 Approximation Algorithms for Embedding Metrics into Two-dimensional Space Mihai Badoiu 4:15 - 5:00 Generic Global Rigidity Bob Connelly 5:00 - 5:15 Break 5:15 - 6:00 Approximating steiner k-cuts Chandra Chekuri Thursday, August 21, 2003 9:00 - 9:30 Breakfast and registration 9:30 - 11:00 Tutorial: Lipschitz quotient maps between Banach spaces Bill Johnson 11:00 - 11:15 Break 11:15 - 12:15 The analogies between the structure theory of finite metric spaces and the local theory of Banach spaces- past, present and future Assaf Naor 12:15 - 1:30 Lunch 1:30 - 2:15 Preduals of spaces of Lipschitz functions and applications to Lipschitz structure Nigel Kalton 2:15 - 3:00 TBA Stephen Semmes 3:00 - 3:30 Break 3:30 - 4:15 A unified approach to Lipschitz extension James R. Lee 4:15 - 5:15 Graph classes defined by distance properties Victor Chepoi 5:15 - 6:00 Average distortion Yuri Rabinovich Friday, August 22, 2003 9:00 - 9:30 Breakfast and registration 9:30 - 10:15 Impossibility of dimension reduction in l_1 Bo Brinkman 10:15 - 10:35 The impossibility of dimension reduction in L_1 Assaf Naor 10:35 - 10:50 Break 10:50 - 11:35 The intrinsic dimensionality of graphs Robert Krauthgamer 11:35 - 12:20 Bounded geometries, fractals and low distortion embeddings Anupam Gupta 12:20 - 2:00 Lunch 2:00 - 2:45 On metric Ramsey-type Phenomena Manor Mendel 2:45 - 3:30 Ramsey Theorem for Metric Spaces+ Yair Bartal 4:00 - 4:45 Embedding box metrics in l_p Avner Magen 5:00 - ... Rump session (open problems and short communications) <= 5 minutes per speaker Saturday, August 23, 2003 9:00 - 9:30 Breakfast and registration 9:30 - 11:00 Tutorial: Embeddings and computation over streaming data S. Muthu Muthukrishnan 11:00 - 11:15 Break 11:15 - 12:00 TBA Graham Cormode 12:00 - 1:30 Lunch 1:30 - 1:55 Similarity estimation, rounding algorithms and metric embeddings Moses Charikar 1:55 - 2:20 Experiments with Embedding Earth-Mover Distance into Normed Spaces Piotr Indyk 2:20 - 2:45 Experiments with Random Projections for Machine Learning Dmitriy Fradkin 2:45 - 3:30 Exploiting embeddings of Biosequence Similarity Scores Jeremy Buhler 3:30 - 4:00 Break 4:00 - 4:45 Lower bounds for L_infty approximations in data streams Ravi Kumar 4:45 - 5:10 Tight Lower Bounds for the Distinct Elements Problem David Woodruff 5:10 - 5:55 On the hardness of approximate proximity search for non-metric/non-geometric spaces Cenk Sahinalp Registration Fees: (Pre-registration deadline: August 13, 2003) Regular rate Preregister before deadline $120/day After preregistration deadline $140/day Reduced Rate* Preregister before deadline $60/day After preregistration deadline $70/day Postdocs Preregister before deadline $10/day After preregistration deadline $15/day DIMACS Postdocs $0 Non-Local Graduate & Undergraduate students Preregister before deadline $5/day After preregistration deadline $10/day Local Graduate & Undergraduate students $0 (Rutgers & Princeton) DIMACS partner institution employees** $0 DIMACS long-term visitors*** $0 Registration fee to be collected on site, cash or check only. Our funding agencies require that we charge a registration fee for the workshop. Registration fees cover participation in the workshop, all workshop materials, breakfast, lunch, breaks, and any scheduled social events (if applicable). * College/University faculty and employees of non-profit organizations will automatically receive the reduced rate. Other participants may apply for a reduction of fees. They should email their request for the reduced fee to the Workshop Coordinator at workshop at dimacs.rutgers.edu. Include your name, the Institution you work for, your job title and a brief explanation of your situation. All requests for reduced rates must be received before the preregistration deadline. You will promptly be notified as to the decision about it. ** Fees for employees of DIMACS partner institutions are waived. DIMACS partner institutions are: Rutgers University, Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies. Fees for employees of DIMACS affiliate members Avaya Labs, IBM Research and Microsoft Research are also waived. ***DIMACS long-term visitors who are in residence at DIMACS for two or more weeks inclusive of dates of workshop. ********************************************************* Information on participation, registration, accommodations, and travel can be found at: http://dimacs.rutgers.edu/Workshops/MetricSpaces/ **PLEASE BE SURE TO PRE-REGISTER EARLY** *********************************************************