[CS] Erasmo Tani Dissertation Defense/Jun 18, 2024

[Megan Woodward via cs]

This is an announcement of Erasmo Tani's Dissertation Defense.
===============================================
Candidate: Erasmo Tani

Date: Tuesday, June 18, 2024

Time: 12 pm CT

Remote Location:  https://uchicago.zoom.us/j/97575219537?pwd=VXFoQXNndENWYlVva21sVFdOTE0wdz09

Location: JCL 390

Title: New Algorithmic Results in Clustering and Partitioning

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.

Advisors: 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/cs/attachments/20240617/972d63b3/attachment.html>