<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><span style="-webkit-text-size-adjust: auto;">Departments of Mathematics & Computer Science</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Combinatorics & Theory Seminar</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Tuesday, February 27, 3:30pm</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Location: <b>Ryerson 251</b></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">SPEAKER: </span>Haotian Jiang (Microsoft Research/UChicago)<div style="-webkit-text-size-adjust: auto;"><br><div>TITLE: Sparse Submodular Function Minimization</div><div><br>ABSTRACT: 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. </div><div><br></div><div>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. </div><div><br></div><div>This talk is based on joint work with Andrei Graur and Aaron Sidford, both from Stanford University. </div></div><div dir="ltr"></div></body></html>