[Colloquium] Reminder - Erasmo Tani Candidacy Exam/Nov 30, 2023

[Megan Woodward]

This is an announcement of Erasmo Tani's Candidacy Exam.
===============================================
Candidate: Erasmo Tani

Date: Thursday, November 30, 2023

Time:  12:00 pm CST

Remote Location: https://uchicago.zoom.us/j/99182440755?pwd=VXd1RU9RVnBtMGFVL0xYQjZTKzVpdz09

Location: JCL 390

Title: New Theoretical Results in Algorithmic Clustering and Partitioning

Abstract: 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.

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.

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.

Based on joint works with Konstantinos Ameranis, Antares Chen, Adela DePavia, Olga Medrano Martín del Campo and Lorenzo Orecchia.

Advisor: Lorenzo Orecchia

Committee Members: Lorenzo Orecchia, Yury Makarychev, and Ali Vakilian




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20231130/06d8ae11/attachment.html>