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 *S _{1}*,

*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

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?

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 *workshops@aimath.org*

Plain text announcement or brief announcement.

Go to the
American Institute of Mathematics.

Go to the
list of upcoming workshops.