Algorithms for Recovering Planted r-Colorable Subgraphs
Anand Louis (IISc Bangalore)
| Speaker |
Anand Louis (IISc Bangalore)
|
|---|---|
| When |
Apr 29, 2024
from 02:00 PM to 03:00 PM |
| Where | LH-111 (TIFR CAM) Hybrid mode |
| Add event to calendar |
vCal
iCal
|
Bangalore Probability Seminar
Title
Algorithms for Recovering Planted r-Colorable Subgraphs
Abstract
The problem of finding a clique hidden in a random graph, known as the planted clique problem, is a fundamental problem in study of algorithms. A natural question that arises is what other planted structures can be recovered efficiently? We study the problem of finding an r-colorable subgraph hidden in a random graph.
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 r-colorable 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.