Recovering Planted Subgraphs Using Semidefinite Programming
Abstract: Recovering a subgraph with a specified property hidden in a random graph is a fundamental problem in the study of algorithms and 'beyond worst case analysis'. One of the central problems in this direction of study is the planted clique problem. The seminal work of Alon, Krivelevich and Sudakov (1998) gave an algorithm to compute planted cliques of size \Omega(\sqrt{n}); their algorithm was based on using the graph's spectra. The instance's spectra is not known to be sufficient for recovering other planted structures such planted bipartite graphs, etc. In this talk, I'll present a semidefinite programming based algorithm for exact recovery of \Omega(\sqrt{n \log n}) sized planted bipartite graphs.
Based on joint work with Akash Kumar and Rameesh Paul.
Based on joint work with Akash Kumar and Rameesh Paul.
Speaker Bio
Anand Louis is an Associate Professor at the Indian Institute of Science Bangalore working primarily in the areas of approximation algorithms, fairness, and randomness. He was earlier a post doctoral researcher at the Princeton university after having completed his PhD at Georgia Tech advised by Santosh Vempala. He has taught several courses at the CSA department including approximation algorithms, spectral algorithms, theorists' toolkit, design and analysis of algorithms, as well as deep learning.