The problem of finding a clique hidden in a random graph, known as the planted clique problem, is a fundamental problem in the study of algorithms. There are algorithms known that can recover planted cliques of size $\Omega(\sqrt{n})$. A natural question that arises is what other planted structures can be recovered efficiently? In this talk, I'll present an algorithm that recovers most of the vertices of a r-colorable subgraph of size $\Omega(r \sqrt{n})$ hidden in a random graph. I will also talk about the analogous problem in hypergraphs.
This talk is based on joint works with Pravesh Kothari, Rameesh Paul and Prasad Raghavendra.
Bio: Anand Louis is an Associate Professor in the Department of Computer Science and Automation, Indian Institute of Science, Bengaluru. His research interests are in algorithms and in the theoretical aspects of AI and machine learning. Before joining IISc, he was a postdoctoral researcher at the Princeton University. He obtained his Ph.D. from the Georgia Institute of Technology, Atlanta.
