In recent years, the use and understanding of geometric methods has emerged as a new and influential 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/ε2)) dimensions with a (1+ε)-distortion in distances.
Following the work of Linial, London, and Rabinovich in 1995, 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 for very large data sets, where the sheer size of the data renders several basic problems infeasible. Two paradigms have emerged to combat this intractability: (a) streaming, where algorithms access very large data sets by making multiple passes over the data using very little memory, and (b) sketching, where algorithms operate on compact summaries of the data (sketches) that allow approximate computations to be performed.
There has been a lot of interest and activity in finite metric spaces, streaming, and sketching in the past few years and several advances have been made. Techniques for proving lower bounds in complexity have recently inspired several negative results in the context of metric spaces, streaming, and sketching. For example, many components from the complexity toolkit (communication complexity, Fourier analysis, etc.) have been exploited to make advances on open problems in the theory of finite metrics. In sketching and streaming, fundamental limits on what can be achieved have been based on communication complexity techniques. In fact, techniques based on communication complexity have given rise to sketching lower bounds which in turn imply new metric embedding lower bounds. This is a two-way street. Attempting to show lower bounds on streaming algorithms has motivated the development of product theorems and other new results in communication complexity. However, many challenges remain, including tight bounds for the distortion of embeddings of negative type metrics into L1.
Geometric techniques have also proved useful in showing limits on approximation techniques. For example, local versus global phenomena have been investigated recently in the context of metric embeddings and the constructions of metrics that have emerged have proved to be a crucial building block in integrality gap constructions for lift-and-project mathematical relaxations for a variety of optimization problems. This is a promising direction whose full potential is yet to be reached. The workshop will explore the use of these techniques for more optimization problems, as well as seeking to characterize the limits of optimization problems for which they might be useful.
Next: Call for Participation
Workshop Index
DIMACS Homepage