[Colloquium] Antares Chen MS Presentation/Dec 6, 2023

[Megan Woodward]

This is an announcement of Antares Chen's MS Presentation
===============================================
Candidate: Antares Chen

Date: Wednesday, December 06, 2023

Time: 10:30 am CST

Remote Location: https://uchicago.zoom.us/j/94338822140?pwd=bWN1dGxScmdUMi81NHFaQ0UxUkk2Zz09<https://urldefense.com/v3/__https://uchicago.zoom.us/j/94338822140?pwd=bWN1dGxScmdUMi81NHFaQ0UxUkk2Zz09__;!!BpyFHLRN4TMTrA!87019S-Dd6Tz7mirkQxjKISJanlExKEqKv7Bxhz9ESSha1ZQXFcOCr8xLS9HEdTRlVcG-WqhAZYv2vVpWASFbrJ5Os6TVL1LQFbs$>

Location: TTIC 431

Title: Almost-linear Time Hypergraph Partitioning via Cut-Matching Games

Abstract: In this presentation, we study the problem of minimizing hypergraph ratio-cut objectives given by polymatroidal cut functions, a class of hypergraph partitioning objectives which, as special cases, include minimizing undirected, and directed versions of hypergraph expansion and conductance.

We introduce an efficient algorithm for finding an $O(\log n)$-approximation to the minimum ratio-cut problem for polymatroidal cut functions. We first define and construct efficient solvers for a local version of the minimum ratio-cut problem called ratio-cut improvement. This can be seen as a natural generalization of Andersen & Lang's cut-improvement problem to the hypergraph setting. We then demonstrate how to generalize the Cut-Matching game framework of Khandekar et. al. to "boost" our cut-improvement solver and produce an $O(\log n)$-approximation algorithm for minimum ratio-cut. Our algorithms run in almost-linear time when the ratio-cut objectives correspond to the aforementioned special cases.

A technical byproduct of this work is that it interprets the Cut-Matching game as an instance of Mirror Descent, a frequently used family of first-order optimization methods used to minimize non-smooth convex functions. Using this interpretation, we show that certain combinatorial restrictions classically required by the Cut-Matching game, such as requiring the cut player to play balanced cuts, are not strictly necessary. We believe this may be of independent interest.

Work based on: https://arxiv.org/abs/2301.08920<https://urldefense.com/v3/__https://arxiv.org/abs/2301.08920__;!!BpyFHLRN4TMTrA!87019S-Dd6Tz7mirkQxjKISJanlExKEqKv7Bxhz9ESSha1ZQXFcOCr8xLS9HEdTRlVcG-WqhAZYv2vVpWASFbrJ5Os6TVDdNVVg_$>

Advisors: Lorenzo Orecchia

Committee Members: Julia Chuzhoy, Lorenzo Orecchia, and Madhur Tulsiani
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20231205/ff3c726b/attachment-0001.html>