Wednesday / CS Seminar

September 25th / 12:00 PM

Hybrid / Mudd 3514

Speaker

Miklos Z. Racz (Miki Racz)

Talk Title

Recent Advances in Learning in Networks: The Interplay Between Community Recovery and Graph Matching

Abstract

Community recovery and graph matching are two fundamental inference tasks on networks. I will discuss recent work that studies the interplay between them, focusing on the natural setting of edge-correlated stochastic block models. We determine the information-theoretic thresholds for both graph matching and community recovery. In particular, this uncovers and characterizes a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though this is impossible using a single graph and exact graph matching is also impossible. Furthermore, we develop an efficient algorithm for these tasks under a condition on the correlation strength that is conjectured to be necessary. This is based on joint works with Shuwen Chai, Julia Gaudio, Anirudh Sridhar, and Jifan Zhang.

Biography

Miklos Z. Racz is an assistant professor at Northwestern University, jointly in the Department of Statistics and Data Science and the Department of Computer Science. Before joining Northwestern, he received his PhD in Statistics from UC Berkeley, he was a postdoc in the Theory Group at Microsoft Research, Redmond, and was then an assistant professor at Princeton University. Miki's research lies at the interface of probability, statistics, computer science, and information theory, with a focus on combinatorial statistics, discrete probability, and applied probability. Miki's research and teaching has been recognized by Princeton's Howard B. Wentz, Jr. Junior Faculty Award, a Princeton SEAS Innovation Award, and an Excellence in Teaching Award.

---

Zoom: https://northwestern.zoom.us/j/94751868037

Panopto: https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=82943682-aad1-43d3-85a6-b1ef00ee3f53