<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">This is an announcement of Antares Chen's MS Presentation</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">===============================================</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Candidate: Antares Chen</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Date: Wednesday, December 06, 2023</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Time: 10:30 am CST</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Remote Location: <a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/94338822140?pwd=bWN1dGxScmdUMi81NHFaQ0UxUkk2Zz09__;!!BpyFHLRN4TMTrA!87019S-Dd6Tz7mirkQxjKISJanlExKEqKv7Bxhz9ESSha1ZQXFcOCr8xLS9HEdTRlVcG-WqhAZYv2vVpWASFbrJ5Os6TVL1LQFbs$" class="">https://uchicago.zoom.us/j/94338822140?pwd=bWN1dGxScmdUMi81NHFaQ0UxUkk2Zz09</a></span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Location: TTIC 431</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Title: Almost-linear Time Hypergraph Partitioning via Cut-Matching Games</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">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 class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">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 class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">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 class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Work based on: <a href="https://urldefense.com/v3/__https://arxiv.org/abs/2301.08920__;!!BpyFHLRN4TMTrA!87019S-Dd6Tz7mirkQxjKISJanlExKEqKv7Bxhz9ESSha1ZQXFcOCr8xLS9HEdTRlVcG-WqhAZYv2vVpWASFbrJ5Os6TVDdNVVg_$" class="">https://arxiv.org/abs/2301.08920</a></span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Advisors: Lorenzo Orecchia</span></div>
<div class=""><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class="">Committee Members: Julia Chuzhoy, Lorenzo Orecchia, and Madhur Tulsiani</span></div>
<div class="">
<div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
<div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
<br class="">
</div>
</div>
<br class="Apple-interchange-newline">
</div>
<br class="">
</body>
</html>