Quantitative and Computational Aspects of Metric Geometry

Organizing Committee | Scientific Overview | Speaker List

Application/Registration | Contact Us

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

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

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:
Website: http://www.ipam.ucla.edu/programs/mg2009/

Back to Top