<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
p.p1, li.p1, div.p1
{mso-style-name:p1;
margin:0in;
font-size:8.5pt;
font-family:Helvetica;
color:#FF9400;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="p1"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
</div>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Nguyen Thuy Duong Vuong</span></b><b><span style="font-size:11.0pt;font-family:Helvetica"><o:p></o:p></span></b></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica">Stanford University</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> </span></b><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> </span></b><img width="141" height="141" style="width:1.4687in;height:1.4687in" id="Picture_x0020_5" src="cid:image001.jpg@01D85008.3F3D92F0"><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt">Tuesday, April 18, 2022 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;background:yellow;mso-highlight:yellow">Kent Chemical Laboratory, Room 107</span></b><b><span style="font-size:11.0pt"><o:p></o:p></span></b></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><i><span style="font-size:11.0pt">Title:</span></i><span style="font-size:11.0pt">
</span><b><span style="font-size:11.0pt;font-family:"Arial",sans-serif">“</span></b><b><span style="font-size:11.0pt;font-family:Helvetica">From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization</span></b><b><span style="font-size:11.0pt;font-family:"Arial",sans-serif">”<o:p></o:p></span></b></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><i><span style="font-size:12.0pt;color:black">Abstract:
</span></i><span style="font-size:12.0pt;color:black">"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. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">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."<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Based on joint work with Nima Anari.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Times New Roman",serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;color:black">Bio:</span></i><span style="font-size:12.0pt;color:black"> NguyenThuy-Duong "June" Vuong is a third year PhD student at Stanford University, working with Nima Anari and Moses Charikar. She works
on geometry of polynomials, with applications in sampling and optimization algorithms over combinatorial domain.</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Host:
</span></b><b><span style="font-size:14.0pt">Madhur Tulsiani</span></b><span style="font-size:14.0pt"><o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt">-- </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Jose J Fragoso</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Project Assistant IV</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Computer Science Department</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">5730 S. Ellis – Room 200C</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Chicago, IL. 60637</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">jfragoso@uchicago.edu</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">(773) 702-6614</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">(773) 702-8487 FAX</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"><img width="92" height="92" style="width:.9583in;height:.9583in" id="Picture_x0020_1" src="cid:image003.png@01D83D68.0E6B3630" alt="signature_1572818061"></span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
</div>
</body>
</html>