#
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

## 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 *S*_{1}, *S*_{2}, *S*_{3}, it is known that

*volume(S*_{3}) ≥ (2 d(S_{1},S_{2})/Diameter(K))
min{volume(S_{1}), volume(S_{2})}

where *d(S*_{1},S_{2}) is the smallest distance between points in *S*_{1} and *S*_{2}. 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(XX*^{T}) 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 *R*^{n} 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.