IPAM Institute for Pure and Applied Mathematics UCLA NSF
Skip Navigation Links
Main Page
Program Poster PDF
Lodging & Air Travel
Schedule and Presentations

Quantitative and Computational Aspects of Metric Geometry

January 12 - 16, 2009

Organizing Committee | Scientific Overview | Speaker List

Application/Registration | Contact Us

Organizing Committee

Subhash Khot (New York University)
Bruce Kleiner (Yale University)
Manor Mendel (The Open University of Israel)
Assaf Naor (New York University)
Yuval Rabani (Technion - Israel Institute of Technology)

Back to Top

Scientific Overview

Following the seminal work on the non-linear theory of Banach spaces in the 1970s and 1980s, we have witnessed a recent revival of interest in the rich structure and profound properties of metric spaces. Much contemporary research on metric geometry is motivated by the discovery of unexpected connections linking fundamental questions in geometry and analysis with combinatorial optimization, computational complexity, and statistics. This has led to the emergence of an impressive and growing repertoire of common problems and techniques.

Some of the most striking examples of this trend evolved from the simple observation that an $n$-point subset of $L_1$ is a convex combination of cut semi-metrics, up to scaling. Thus, the properties of finite subsets of $L_1$ are closely connected to cut-related graph theoretic optimization problems, such as expansion. In particular, computational methods for bounding the optima of NP-hard optimization problems often lead to the formulation of discrete analogues of embedding problems in Banach space theory. Studying the quantitative properties of Lipschitz and bi-Lipschitz maps into Banach spaces plays a pivotal role in both areas, mutually influencing each other. For example, the notion of padded decompositions gradually got refined through its application to problems in distributed computing, approximation algorithms, construction of embeddings into Hilbert space, and metric Ramsey theory.

In the same vein, the design of hardness of approximation reductions involves examining the cut structure of the binary cube or quotients of the binary cube, using bounds on the Fourier coefficients of Boolean functions. The same tools are extremely useful in proving results on non-embeddability into $L_1$. A recent breakthrough in geometric analysis studies the structure of cuts of the Heisenberg group. Substantial progress on non-embeddability questions is implied, and this promising direction may bear significant consequences in computational complexity theory.

Group theorists have been studying groups as geometric objects for several decades. The achievements of geometric group theory are numerous and profound. Metric embedding problems for discrete groups are particularly fruitful in the study of the Novikov conjecture, and recent work uses expanders and randomized constructions. The computation of Hilbert compression exponents of finitely generated groups has several algebraic consequences, and recent results are based on applications to these problems of methods from Banach space theory (Markov type), probability, and representation theory.

Finally, it is noteworthy to mention the more obvious relation between quantitative and computational aspects of metric spaces, namely, the study of problems arising in the context of processing data endowed with a geometric representation. Due to the proliferation of massive data sets in commerce, web, molecular biology, and other areas, computationally efficient methods for finding meaningful patterns in such data are acutely needed. Analytic and algorithmic results in metric geometry play a crucial role in this field.

This workshop will include a poster session; a request for posters will be sent to registered participants in advance of the workshop.

Back to Top

Confirmed Speakers

Nir Ailon (Google Research)
Alexandr Andoni (Massachusetts Institute of Technology)
Sanjeev Arora (Princeton University)
Moses Charikar (Princeton University)
Guy David (Université Paris-Sud 11)
Uriel Feige (Weizmann Institute of Science)
Anupam Gupta (Carnegie-Mellon University)
William Johnson (Texas A&M University - College Station)
Subhash Khot (New York University)
Robert Krauthgamer (Weizmann Institute of Science)
James Lee (University of Washington)
Nathan (Nati) Linial (Hebrew University)
Konstantin Makarychev (IBM Thomas J. Watson Research Center)
Yury Makarychev (Microsoft Research New England)
Assaf Naor (New York University)
Yuval Rabani (Technion - Israel Institute of Technology)
Gideon Schechtman (Weizmann Institute of Science)
Leonard Schulman (California Institute of Technology)
Tatiana Toro (University of Washington)
Alain Valette (Université de Neuchâtel)

Back to Top

Back to Top

Contact Us:

Institute for Pure and Applied Mathematics (IPAM)
Attn: MG2009
460 Portola Plaza
Los Angeles CA 90095-7121
Phone: 310 825-4755
Fax: 310 825-4756
Email: ipam@ucla.edu
Website: http://www.ipam.ucla.edu/programs/mg2009/

Back to Top

NSF Math Institutes   |   Webmaster