[Colloquium] Guest Speaker @ TTI-C TODAY (2/24 @ 10:00am)

[Katherine Cumming]

**********TTI-C Guest Speakers Today***********
                       February 24, 2006
 
Speaker: Santosh Vempala, MIT
Speaker's home page:  <http://www-math.mit.edu/~vempala/>
http://www-math.mit.edu/~vempala/
 
Date: Friday, February 24, 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title:  
 
Dispersion of Mass and the Complexity of Randomized Algorithms
 
Abstract:
 
How much can randomness help computation?  Motivated by this question, we
analyze a notion of dispersion and connect it to asymptotic convex geometry.
Two of the most appealing conjectures in the latter field are (i) slicing
(or isotropic constant) and (ii) variance.  Together they imply that for a
random point X from an isotropic convex body in n-space, the variance of
|X|^2 is O(n).  We prove a reverse inequality: for any isotropic convex
polytope with at most poly(n) facets, the variance of |X|^2 is AT LEAST n/ln
n (up to a constant).  In fact, the lower bound holds for any polytope of
unit volume with poly(n) facets contained in the ball of radius poly(n).  It
implies that in order for most of such a convex polytope to be contained
between two concentric spheres, their radii have to differ by about
1/\sqrt{\log n}; in contrast, most of a unit-volume ball lies in between two
spheres whose radii differ by only about 1/\sqrt{n}.  This geometric
dispersion leads to linear and quadratic lower bounds on the randomized
complexity of some basic algorithmic problems.
 
This is joint work with Luis Rademacher. 
 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060224/1362c105/attachment.htm