[Colloquium] UPDATE (Part II) - CS Theory Seminar - Haotian Jiang, February 26, 2024

[Jose J Fragoso]

My apologies for the multiple emails.


UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Haotian Jiang, PhD
Microsoft Research/UChicago


 [A person wearing glasses and smiling  Description automatically generated]

Tuesday, February 26, 2024 at 3:30pm
Room: Ryerson 251



Title: Sparse Submodular Function Minimization

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. 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.

This talk is based on joint work with Andrei Graur and Aaron Sidford, both from Stanford University.

Bio: I’m currently a Postdoctoral Researcher at Microsoft Research, Redmond. In December 2022, I 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. I am broadly interested in theoretical computer science and applied mathematics. My 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.



Host: Alexander Razborov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240223/64b17a98/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 75768 bytes
Desc: image001.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240223/64b17a98/attachment-0001.png>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240223/64b17a98/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240223/64b17a98/attachment-0003.txt>