<html><head><meta http-equiv="content-type" content="text/html; charset=us-ascii"></head><body dir="auto"><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt; font-family: Helvetica;">Haotian Jiang, PhD</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt; font-family: Aptos, sans-serif;">Microsoft Research/UChicago</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><b><span style="font-size: 11pt; font-family: Helvetica;"><img width="240" height="244" id="Picture_x0020_3" src="cid:ABCECD2F-DE25-448C-811D-409F9AE73C94" alt="image001.png" _mf_state="1" title="null" style="width: 2.5in; height: 2.5416in;"></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt; background: yellow;"><span dir="ltr">Tuesday</span></span></b><b><span style="font-size: 12pt;"><span dir="ltr">, February 26, 2024 at 3:30pm</span></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt;">Room: Ryerson 251</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; font-family: Aptos, sans-serif;">T<span style="color: rgb(33, 33, 33);">itle:</span></span></i></b><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"> </span><span style="font-size: 12pt;">Sparse Submodular Function Minimization</span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);">Abstract:</span></i></b><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"> </span><span style="font-size: 12pt; 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><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; background: white;">This talk is based on joint work with Andrei Graur and Aaron Sidford, both from Stanford University.</span></p><div dir="ltr"></div></body></html>