Algorithms for Recovering Planted rColorable Subgraphs
Speaker 
Anand Louis (IISc Bangalore)


When 
Apr 29, 2024
from 02:00 PM to 03:00 PM 
Where  LH111 (TIFR CAM) Hybrid mode 
Add event to calendar 
vCal iCal 
For the planted clique problem, there are algorithms known that can recover planted cliques of size \Omega(\sqrt{n}). In this talk, I'll present an algorithm that recovers most of the vertices of planted rcolorable subgraphs of size \Omega(r \sqrt{n}). The algorithm is based on a novel semidefinite programming relaxation of the problem and a rounding algorithm for it. For the case when then planted subgraph is a regular bipartite graph, I'll present an algorithm that recovers the entire planted subgraph if its size is \Omega(\sqrt{n}). This improves on the previous algorithm by Kumar et al. (2022)
This talk is based on joint work with Rameesh Paul and Prasad Raghavendra.