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.