[Theory] [Theory Lunch] Max Ovsiankin, Wednesday 3/2 12:30pm-1:30pm, JCL 390.

[Adela DePavia]

Date: March 2nd, Wednesday
Time: 12:30pm CT
Location: JCL 390

Speaker:  Max Ovsiankin

Title: Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

Zoom: [link<https://www.google.com/url?q=https%3A%2F%2Fuchicago.zoom.us%2Fj%2F97375149992%3Fpwd%3DYmNGa1FoaW1WOXVaQ1UxcVBWMjhVdz09&sa=D&ust=1646512430502000&usg=AOvVaw13FTypdW6t1Zcb49FcCVaI>]

Abstract: John's theorem is a useful result that says that any symmetric convex body can be well-approximated by some ellipsoid with an approximation factor that is the square root of the dimension of the body. Ellipsoidal approximations more generally have been applied to approximating the volume of convex bodies and sampling from them using Markov chains, and have been applied in other areas such as online optimization. We present new streaming algorithms for finding ellipsoidal approximations when these convex bodies are polytopes. These algorithms are well-suited to low-memory or online settings, and their runtime matches that of the best known algorithms for the offline setting. The approximation factor differs from the offline solution only by a factor sub-logarithmic in the aspect ratio of the polytope. Based on joint work with Naren Manoj and Yury Makarychev.

[Theory Lunch Webpage<https://orecchia.net/event/theory-lunch/>]
[Theory Lunch Calendar<https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago>]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220228/26956468/attachment.html>