Algorithmic Convex Geometry

November 5 to November 9, 2007

at the

American Institute of Mathematics, Palo Alto, California

organized by

Assaf Naor and Santosh Vempala

This workshop, sponsored by AIM and the NSF, is motivated by algorithms and draws heavily on probability (especially the theory of stochastic processes), convex geometry and functional analysis. The workshop will bring together leading researcher in these areas. On one hand, algorithms researchers will clearly benefit from this. What is equally exciting is that algorithmic insights have started returning the favor --- they have led to questions and advances in convex geometry and probability, notably in the form of isoperimetric inequalities and rapidly-mixing geometric random walks. The workshop will identify and focus on such directions (two specific problems are stated below) showing new directions for analysts, geometers and probabilists. It is our hope that such a confluence will make substantial progress in shaping this field.

Geometric random walks are maturing into a powerful tool for algorithm design (see the survey by Vempala). Their analysis hinges on isoperimetric inequalities for the state space. For all partitions of the state space into measurable subsets with a fixed proportion of measure, what is the minimum possible measure of the separating surface? E.g., for a convex body K and any partition S1, S2, S3, it is known that

volume(S3) ≥ (2 d(S1,S2)/Diameter(K)) min{volume(S1), volume(S2)}

where d(S1,S2) is the smallest distance between points in S1 and S2. While this bound is tight in terms of the diameter, it has been conjectured that the coeffient (2/Diameter(K)) can be replaced by c/√λ where c is an absolute constant and λ is the largest eigenvalue of the inertia matrix of K, i.e. E(XXT) for a random point X from K.

Another direction of research involves a different area of geometry, Riemannian manifolds. Consider the following random walk: at a point x on a manifold, we pick a random point in the unit ball in the tangent space and go to the image of this on the manifold. Is this walk rapidly mixing for any manifold with nonnegative curvature? Even for convex bodies, it suggests an elegant procedure: at a current point x, pick a random point y in a ball of some fixed radius, go in the direction of y till you reach y or hit the boundary of the body; in the latter case, reflect the point about the tangent at the boundary and continue.

Convexity itself leads to new questions, e.g., can convexity of a compact set in Rn be efficiently tested, i.e., is there a short proof that a set is (approximately) convex, e.g. by testing random low-dimensional sections of it?

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email

Plain text announcement or brief announcement.

Go to the American Institute of Mathematics.
Go to the list of upcoming workshops.