Nearly Optimal Deterministic Algorithms Via M-Ellipsoids

Computer Science/Discrete Mathematics Seminar I
Topic:Nearly Optimal Deterministic Algorithms Via M-Ellipsoids
Speaker:Santosh Vempala
Affiliation:Georgia Institute of Technology
Date:Monday, January 30
Time/Room:11:15am - 12:15pm/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.