[Colloquium] Erasmo Tani Dissertation Defense/Jun 18, 2024
via Colloquium
colloquium at mailman.cs.uchicago.edu
Tue Jun 4 10:18:48 CDT 2024
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
More information about the Colloquium
mailing list