Computer Science/Discrete Mathematics Seminar I

Submitted by admin on Wed, 01/09/2013 - 19:01
Nearly Optimal Deterministic Algorithms Via M-Ellipsoids
Series: 
Computer Science/Discrete Mathematics
Santosh Vempala
Georgia Institute of Technology
Date & Time: 
Mon, 01/30/2012 - 11:15 - 12:15
Location: 
S-101

Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex bodies, finding the shortest lattice vector under general norms and integer programming.

terms: