(Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs

Algorithms Seminar
Speaker Name
Tselil Schramm
Date and Time
-
Location
LSRC D344
Notes
Lunch served at 12pm.
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.

Short 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.

Host
Debmalya Panigrahi