<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;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@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="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span> <o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102"> </span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><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;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">Haotian Jiang, PhD</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif">Microsoft Research/UChicago</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><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;color:black"> </span></b><b><span style="font-size:11.0pt;font-family:Helvetica"><img width="240" height="244" style="width:2.5in;height:2.5416in" id="Picture_x0020_3" src="cid:image001.png@01DA64D5.B8323240" alt="A person wearing glasses and smiling
Description automatically generated"></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;color:black;background:yellow">Monday, February 26, 2024 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Room – Ryerson 251</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"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Title:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">
</span><span style="font-size:12.0pt">Sparse Submodular Function Minimization</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Abstract:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">
</span><span style="font-size:12.0pt;color:black;background:white">We discuss the problem of minimizing a submodular function (defined on an n-element ground set) that is guaranteed to have a k-sparse minimizer. I will present a weakly polynomial time parallel
algorithm with \poly(k)-depth and a strongly polynomial time algorithm that makes n \poly(k) queries to an evaluation oracle. When k is small, our algorithms have sub-linear parallel depth or sub-quadratic evaluation oracle query complexities. All previous
algorithms for this problem have at least linear parallel depth and make at least a quadratic number of queries. In contrast to state-of-the-art weakly- and strongly-polynomial time algorithms for SFM that all apply cutting plane methods, our algorithms use
first-order methods. We introduce what we call sparse dual certificates, which encode information on the sparse minimizers, and our algorithms provide new algorithmic tools for allowing first-order optimization methods to efficiently compute them.
</span><span style="font-size:12.0pt;background:white"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black;background:white">This talk is based on joint work with Andrei Graur and Aaron Sidford, both from Stanford University.</span><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"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Bio</span></i></b><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif">:
</span></i></b><span style="font-size:12.0pt;color:#202020;letter-spacing:-.1pt">He is currently a Postdoctoral Researcher at Microsoft Research, Redmond. In December 2022, he obtained his PhD from the Paul G. Allen School of Computer Science & Engineering
at the University of Washington under the supervision of Yin Tat Lee. He is broadly interested in theoretical computer science and applied mathematics. His primary area of expertise is the design and analysis of algorithms for continuous and discrete optimization
problems, and algorithm design through the lens of discrepancy theory.</span><o:p></o:p></p>
<p><span style="color:black"> </span></p>
<p style="margin-bottom:12.0pt"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Host:<span class="apple-converted-space"> A</span></span></b><span class="apple-converted-space"><b><span style="font-size:12.0pt;font-family:Helvetica">lexander
Razborov</span></b></span></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>