<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div class="elementToProof" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<div tabindex="-1" class="fEEQbbifEC8quzJXH0sd TiApUvaZOn0aLkSUHRf7 allowTextSelection">
<div dir="ltr">
<div dir="ltr">
<div style="color:black; font-size:12pt; font-family:Calibri,Arial,Helvetica,sans-serif">
<span style="background-color:white; margin:0"><span style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="margin:0"><span style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><b>Date:</b> April
20th, Wednesday</font></span></span></span></span></div>
<div style="color:black; font-size:12pt; font-family:Calibri,Arial,Helvetica,sans-serif">
<div style="background-color:white; margin:0">
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0">
<div style="margin:0">
<div style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><b>Time: </b>12:30pm CT</font></div>
<div style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><b>Location: </b>JCL 298 **
<br>
</font></div>
<div dir="auto" style="color:#313131; font-size:16px; margin:0; word-spacing:1px">
<b><font style="font-size:1.13em"><br>
</font></b></div>
<div dir="auto" style="color:#313131; font-size:16px; margin:0; word-spacing:1px">
<b><font style="font-size:1.13em">Speaker: June Vuong<span style="background-color:rgb(255,255,0)"><br>
</span></font></b></div>
<div dir="auto" style="color:#313131; font-size:16px; margin:0; word-spacing:1px">
<b><font style="font-size:1.13em"><br>
</font></b></div>
<div dir="auto" style="color:#313131; font-size:16px; margin:0; word-spacing:1px">
<font size="4"><br>
</font></div>
</div>
<div style="margin:0"><b style="color:#313131; font-size:16px; word-spacing:1px"><font style="font-size:1.13em">Title: <span style="box-sizing:border-box">From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization</span></font></b></div>
<div style="margin:0"><b style="color:#313131; font-size:16px; word-spacing:1px"><font style="font-size:1.13em"><br>
</font></b></div>
<div style="margin:0"><span style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><b>Zoom: </b><a href="https://uchicago.zoom.us/j/96834334557?pwd=VVBXWlBWMjlNSGpQUEZub09raHBXZz09" title="https://uchicago.zoom.us/j/96834334557?pwd=VVBXWlBWMjlNSGpQUEZub09raHBXZz09">[link</a>]</font></span></div>
<div style="margin:0"><span style="color:rgb(49,49,49); word-spacing:1px; font-size:13pt"><b><br>
</b></span></div>
<div style="margin:0"><span style="color:rgb(49,49,49); word-spacing:1px; font-size:13pt"><b>Abstract:</b></span><b style="font-family:inherit; font-style:inherit; font-variant-caps:inherit; color:rgb(49,49,49); font-size:1.13em; word-spacing:1px"> </b><span style="font-size:1.13em; word-spacing:1px; font-family:"Open Sans","Clear Sans","Helvetica Neue",Helvetica,Arial,"Segoe UI Emoji",sans-serif; margin-top:0.8em; margin-bottom:0.8em; box-sizing:border-box; color:rgb(51,51,51)!important"><span style="box-sizing:border-box">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 </span><span style="display:inline-block; box-sizing:border-box">\mu( . )</span><span style="box-sizing:border-box">. More precisely we show that if t-step down-up random walks have spectral gap
at least inverse polynomially large, then </span><span style="display:inline-block; box-sizing:border-box">t</span><span style="box-sizing:border-box">-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.</span></span></div>
<div style="margin:0">
<div dir="auto" style="margin:0"><font style="color:#313131; font-size:1.13em; word-spacing:1px">
<div style="color:rgb(51,51,51)!important; font-family:Open Sans,Clear Sans,Helvetica Neue,Helvetica,Arial,Segoe UI Emoji,sans-serif; background-color:white!important; margin:0.8em 0px; box-sizing:border-box">
<span style="box-sizing:border-box">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."</span></div>
</font></div>
<div dir="auto" style="margin:0"><font style="color:#313131; font-size:1.13em; word-spacing:1px"><span style="color:rgb(51,51,51)!important; font-family:Open Sans,Clear Sans,Helvetica Neue,Helvetica,Arial,Segoe UI Emoji,sans-serif; background-color:white!important; margin:0.8em 0px; box-sizing:border-box"><span style="box-sizing:border-box">Based
on joint work with Nima Anari.</span></span><span style="color:#201F1E; font-size:12pt; font-family:trebuchet ms,sans-serif; background-color:white; margin:0; word-spacing:0px"></span></font></div>
<div dir="auto" style="margin:0"><font style="color:#313131; font-size:1.13em; word-spacing:1px"><span style="color:#201F1E; font-size:15px; font-family:trebuchet ms,sans-serif; background-color:white; margin:0; word-spacing:0px"><br>
</span></font></div>
<div dir="auto" style="margin:0"><font face="trebuchet ms,sans-serif"><b>COVID Policy:<span style="margin:0"> </span></b>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. </font></div>
</div>
</div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0"><font size="4"><br>
</font></div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="font-size:large; margin:0">[<a href="https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!oOnZ3-9vk_IPd8KFkxpESFmuvq-esvE12qbIVPh8cOicyNKum5xoCKMZ3ZHqkvy7BHo$" data-auth="NotApplicable" title="https://orecchia.net/event/theory-lunch/" style="margin:0"><span style="margin:0"><span style="margin:0">Theory</span></span> <span style="margin:0">Lunch</span> Webpage</a>]<br>
[<a href="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$" data-auth="NotApplicable" title="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" style="margin:0"><span style="margin:0"><span style="margin:0"><span style="margin:0"><span style="margin:0">Theory</span></span></span></span><span style="margin:0"> </span><span style="margin:0"><span style="margin:0">Lunch</span></span><span style="margin:0"> </span>Calendar</a>]</span></div>
</div>
</div>
</div>
</div>
</div>
<br>
</div>
</body>
</html>