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

Presented on September 24, 2018 at 11:00 a.m. in the Pettit Microelectronics Research Center, room 102A&B.Tselil Schramm is a postdoc in theoretical computer science at Harvard and MIT. She recently graduated with a PhD at the U.C. Berkeley Theory Group, where she was advised by Prasad Raghavendra and Satish Rao.Runtime: 48:43 minutesThe 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