<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="">
This is an announcement of Erasmo Tani's Dissertation Defense.<br class="">
===============================================<br class="">
Candidate: Erasmo Tani<br class="">
<br class="">
Date: Tuesday, June 18, 2024<br class="">
<br class="">
Time: 12 pm CT<br class="">
<br class="">
Remote Location: <a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/97575219537?pwd=VXFoQXNndENWYlVva21sVFdOTE0wdz09__;!!BpyFHLRN4TMTrA!83G-sYMvwW842tI7XPI-SzDg02JrctezaTq7w5N7J8oG2yJai7zezkiGwq6CjZs78t7NGCdNRXblW8QY_nltBFI2ccePdKNm-y9Bd4wI0g$" class="">https://uchicago.zoom.us/j/97575219537?pwd=VXFoQXNndENWYlVva21sVFdOTE0wdz09</a><br class="">
<br class="">
Location: JCL 390<br class="">
<br class="">
Title: New Algorithmic Results in Clustering and Partitioning<br class="">
<br class="">
Abstract: Clustering and partitioning tasks have found widespread applications across computing. In machine learning, clustering represents the quintessential unsupervised learning task: grouping similar data points to identify structure in data. In operations
research and combinatorial optimization, one is often interested in finding bottlenecks in a network, to identify possible weakness and points of failure. In this work, we discuss recent progress in better understanding computational aspects of clustering
and partitioning. First, we cover approximation algorithms for graph partitioning tasks, focusing on the theory behind finding small vertex separators: few vertices which, when removed, disconnect the graph into large pieces. We also outline a recently uncovered
connection between this problem and the fastest mixing random walk process on a graph with a target distribution. We then discuss some algorithmic results in partitioning hypergraphs. We design approximation algorithms for hypergraph generalizations of the
minimum conductance cut problem by leveraging and extending techniques from spectral graph theory to the hypergraph regime. Finally, we will address the problem of learning partitions in an interactive way, by querying a same-cluster oracle, which determines
whether two points belong to the same cluster. In this context we develop and analyze novel error-resistant algorithms, and provide complementary lower bounds.<br class="">
<br class="">
Advisors: Lorenzo Orecchia<br class="">
<br class="">
Committee Members: Lorenzo Orecchia, Yury Makarychev, and Ali Vakilian<br class="">
<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="">
<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="Apple-interchange-newline">
</div>
<br class="Apple-interchange-newline">
</div>
<br class="Apple-interchange-newline">
</div>
<br class="Apple-interchange-newline">
</div>
<br class="Apple-interchange-newline">
<br class="Apple-interchange-newline">
</div>
<br class="">
</body>
</html>