<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">This is an announcement of Antares Chen's MS Presentation</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">===============================================</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Candidate: Antares Chen</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Date: Wednesday, December 06, 2023</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Time: 10:30 am CST</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Remote Location: https://uchicago.zoom.us/j/94338822140?pwd=bWN1dGxScmdUMi81NHFaQ0UxUkk2Zz09</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Location: TTIC 431</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Title: Almost-linear Time Hypergraph Partitioning via Cut-Matching Games</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">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.</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">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.</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">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.</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Work based on: https://arxiv.org/abs/2301.08920</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Advisors: Lorenzo Orecchia</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Committee Members: Julia Chuzhoy, Lorenzo Orecchia, and Madhur Tulsiani</span></div>
<div id="Signature">
<div style="background-color: rgb(255, 255, 255);"></div>
</div>
</body>
</html>