[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

Haotian Jiang, PhD
Microsoft Research/UChicago
 
 
 
 
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240226/d3d58cc2/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 75768 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240226/d3d58cc2/attachment-0001.png>