Faculty Recruiting Support CICS

Theory Seminar - Near-Optimal Learning of Joint Alignments and Clusters with a Faulty Oracle

22 Mar
Tuesday, 03/22/2022 11:30am to 12:20pm
Virtual via Zoom
Theory Seminar

Abstract: In this talk I will discuss state-of-the-art results on two important problems, clustering and learning joint alignments (e.g., of images and shapes) using noisy queries. For the clustering problem, we consider the following model for two clusters: we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability $0 0$ one obtains the correct answer, and with the remaining probability one obtains a uniformly random incorrect answer. We provide an efficient algorithm that learns the joint alignment with high probability, and simplifies the prior state-of-the-art algorithm due to Chen and Candes. I will conclude with some open problems. This presentation is based off of joint work with Michael Mitzenmacher (Harvard), Kasper Green Larsen (Aarhus).

Bio: Charalampos Tsourakakis is an assistant professor in computer science at Boston University and a research associate at Harvard. Dr. Tsourakakis obtained his PhD in Algorithms, Combinatorics and Optimization at Carnegie Mellon under the supervision of Alan Frieze, was a postdoctoral fellow at Brown University and Harvard under the supervision of Eli Upfal and Michael Mitzenmacher respectively. Before joining Boston University, he worked as a researcher in the Google Brain team. He has received the 10-year highest impact paper award from IEEE, has won a best paper award in IEEE Data Mining, has delivered three tutorials in the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, and has designed two graph mining libraries for large-scale graph mining, one of which has been officially included in Windows Azure. His research focuses on large-scale graph mining, and machine learning.

.Join the Seminar

The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.