[Theory] Student Theory Lunch: happening in an hour! Note the change in location only for this week:

[Olga Medrano Martin del Campo]

Date: April 20th, Wednesday
Time: 12:30pm CT
Location: JCL 298 **

Speaker: June Vuong


Title: From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization

Zoom: [link<https://uchicago.zoom.us/j/96834334557?pwd=VVBXWlBWMjlNSGpQUEZub09raHBXZz09>]

Abstract: We show a connection between sampling and optimization on discrete domains. For a family of distributions mu defined on size k subsets of a ground set of elements that is closed under external fields, we show that rapid mixing of natural local random walks implies the existence of simple approximation algorithms to find max \mu( . ). More precisely we show that if t-step down-up random walks have spectral gap at least inverse polynomially large, then t-step local search can find max mu( . ) within a factor of k^{O(k)}. As the main application of our result, we show that 2-step local search achieves a nearly-optimal k^{O(k)}-factor approximation for MAP inference on nonsymmetric k-DPPs. This is the first nontrivial multiplicative approximation algorithm for this problem.
We establish the connection between sampling and optimization by showing that an exchange inequality, a concept rooted in discrete convex analysis, can be derived from fast mixing of local random walks."
Based on joint work with Nima Anari.

COVID Policy: As per university policy, masking is not currently required for in-person attendance. Please note that we will have fully masked and social-distanced tables available to accommodate any attendees who would prefer such arrangements. Please contact us if you have any questions or feedback.

[Theory Lunch Webpage<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!oOnZ3-9vk_IPd8KFkxpESFmuvq-esvE12qbIVPh8cOicyNKum5xoCKMZ3ZHqkvy7BHo$>]
[Theory Lunch Calendar<https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!oOnZ3-9vk_IPd8KFkxpESFmuvq-esvE12qbIVPh8cOicyNKum5xoCKMZ3ZHqEX_iTTQ$>]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220420/1ad4ed07/attachment-0001.html>