- This event has passed.
Stochastics and Statistics Seminar
Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs
October 5, 2018 @ 11:00 am - 12:00 pm
Tselil Schramm (Harvard University)
E18-304
Event Navigation
Abstract: The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. We study a popular average-case variant; we deviate from the common heuristic strategy and give the first quasi-polynomial time algorithm, where previously only sub-exponential time algorithms were known.
Based on joint work with Boaz Barak, Chi-Ning Chou, Zhixian Lei, and Yueqi Sheng.
Biography: Tselil Schramm is a postdoc in theoretical computer science at Harvard and MIT, hosted by Boaz Barak, Jon Kelner, Ankur Moitra, and Pablo Parrilo. She obtained her PhD in computer science from U.C. Berkeley under the advisement of Prasad Raghavendra and Satish Rao. Her research interests include inference and average-case problems, optimization via convex programs (especially the sum-of-squares hierarchy), spectral algorithms, spectral graph theory, and more.
