Algorithmic Convex Geometry

November 5 to November 9, 2007

at the

American Institute of Mathematics, San Jose, California

organized by

Assaf Naor and Santosh Vempala

Original Announcement

This workshop 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?

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.