Seminars
View all Seminars | Download ICal for this eventRecovering Planted Subgraphs
Series: CSA Faculty Colloquium
Speaker: Prof. Anand Louis, Associate Professor Dept. of CSA
Date/Time: Sep 06 16:00:00
Location: CSA auditorium [Room No. 104], ground floor
Abstract:
Recovering a subgraph with a specified property hidden in a random graph is a fundamental problem in the study of algorithms. One of the central problems in this direction of study is the planted clique problem, where a clique is planted in an Erdos-Renyi random graph. The seminal work of Alon, Krivelevich and Sudakov (1998) gave an algorithm to compute planted cliques of size ?(??{n}); their algorithm was based on using the graphs spectra. This work has inspired numerous works on this and related problems using tools from random matrix theory, random graphs, -sum-of-squares- framework, convex optimization, and machine learning. I will survey the history and some recent developments related to this problem including some of our recent work.
Speaker 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.
Host Faculty: Prof. Sumit Kumar Mandal