<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
This is an announcement of Erasmo Tani's Candidacy Exam.<br class="">
===============================================<br class="">
Candidate: Erasmo Tani</div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<br class="">
</div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
Date: Thursday, November 30, 2023<br class="">
<br class="">
Time: 12:00 pm CST</div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<br class="">
</div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
Remote Location:<span class="" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 16px;"> </span><a href="https://uchicago.zoom.us/j/99182440755?pwd=VXd1RU9RVnBtMGFVL0xYQjZTKzVpdz09" target="_blank" id="OWAc670ebb4-b955-dda1-e273-2901af9df2e4" class="OWAAutoLink" data-loopstyle="linkonly" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 16px;">https://uchicago.zoom.us/j/99182440755?pwd=VXd1RU9RVnBtMGFVL0xYQjZTKzVpdz09</a> </div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<br class="">
</div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
Location: JCL 390</div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
<br class="">
</div>
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">
Title: <span class="" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">New Theoretical Results in Algorithmic Clustering and Partitioning</span><br class="">
<br class="Apple-interchange-newline">
</div>
Abstract: <span class="" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">Identifying clusters of similar objects is a fundamental task in machine learning. As such, a large body of work has centered around
improving our fundamental understanding of the algorithmic tasks that arise when clustering. In this talk, we will present some recent progress in this area.</span>
<div class="elementToProof"><span class="" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;"><br class="">
In the first part of the talk, we will discuss new results in the theory of partitioning hypergraphs. In particular, we will consider the SUBMODULAR HYPERGRAPH RATIO CUT (SHRC) problem. We will introduce the class of polymatroidal cut functions and describe
novel algorithms for approximating the SHRC problem when the cut functions of the hypergraph in question belong to this class. In particular, we will give a polynomial-time O(\sqrt{\log n})-approximation algorithm and a linear-time O(\log n)-approximation
algorithm for the problem.</span></div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">
<br class="">
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">
In the second part of the talk, we will describe recent progress on learning a hidden partition of a finite set by interacting with an oracle. The central setting of interest will be one in which the oracle answers questions of the form "Are element x and element
y part of the same cluster in the partition?". In particular, we will focus on the problem of exactly recovering the full partition when some fixed number e of queries made to the oracle might return the incorrect answer. We will discuss an analytic framework
for this problem which highlights connections with Rényi-Ulam liar games and correlation clustering, and we will show how we can use it to prove lower bounds to the query complexity of this problem.<br class="">
<br class="">
Based on joint works with Konstantinos Ameranis, Antares Chen, Adela DePavia, Olga Medrano Martín del Campo and Lorenzo Orecchia.</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">
<br class="">
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">
Advisor: Lorenzo Orecchia</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">
<br class="">
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">
Committee Members: Lorenzo Orecchia, Yury Makarychev, and Ali Vakilian</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="">
<br class="Apple-interchange-newline">
</div>
<br class="Apple-interchange-newline">
<br class="Apple-interchange-newline">
</div>
<br class="">
</body>
</html>