<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body>
<div dir="ltr">
<div dir="ltr"><span class="x_elementToProof" style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);"><span style="box-sizing: content-box; margin: 0px; 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></span>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">===============================================</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Candidate: Antares Chen</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Date: Wednesday, December 06, 2023</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Time: 10:30 am CST</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Remote Location:<span class="Apple-converted-space"> </span><a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/94338822140?pwd=bWN1dGxScmdUMi81NHFaQ0UxUkk2Zz09__;!!BpyFHLRN4TMTrA!87019S-Dd6Tz7mirkQxjKISJanlExKEqKv7Bxhz9ESSha1ZQXFcOCr8xLS9HEdTRlVcG-WqhAZYv2vVpWASFbrJ5Os6TVL1LQFbs$" target="_blank" rel="noopener noreferrer" data-auth="NotApplicable" style="box-sizing:content-box;margin:0px">https://uchicago.zoom.us/j/94338822140?pwd=bWN1dGxScmdUMi81NHFaQ0UxUkk2Zz09</a></span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Location: TTIC 431</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; 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 style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; 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 style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; 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 style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; 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 style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Work based on:<span class="Apple-converted-space"> </span><a href="https://urldefense.com/v3/__https://arxiv.org/abs/2301.08920__;!!BpyFHLRN4TMTrA!87019S-Dd6Tz7mirkQxjKISJanlExKEqKv7Bxhz9ESSha1ZQXFcOCr8xLS9HEdTRlVcG-WqhAZYv2vVpWASFbrJ5Os6TVDdNVVg_$" target="_blank" rel="noopener noreferrer" data-auth="NotApplicable" style="box-sizing:content-box;margin:0px">https://arxiv.org/abs/2301.08920</a></span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Advisors: Lorenzo Orecchia</span></div>
<div style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);" dir="ltr">
<span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br style="box-sizing:content-box">
</span></div>
<span class="x_elementToProof" style="text-decoration: none; box-sizing: content-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px; color: rgb(33, 33, 33);"><span style="box-sizing: content-box; margin: 0px; font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">Committee
Members: Julia Chuzhoy, Lorenzo Orecchia, and Madhur Tulsiani</span></span><br>
</div>
</div>
</body>
</html>