Title: Exact Algorithms for Semi-Random k-Clustering
In this talk, I will present an exact algorithm using Semi-Definite programming for the following problem: Given a set of n-nodes and a parameter k (assuming that k divides n), we create a random graph as follows: We choose an arbitrary partition of the nodes into k groups of size n/k. We connect two nodes within the same group with probability p and two nodes belonging to different groups with probability q, where p>q. The goal is to recover the planted k-partition with high probability over the choice of the graph. I will also describe impossibility results as well as algorithmic results for different ranges of p-q.
Assistant Professor in the Computer Science Department at UIUC. She received her PhD at U.C. Berkeley; her advisor was Umesh Vazirani. After her PhD, Prof. Kolla completed a postdoc at the Institute for Advanced Study and at Microsoft Research in Redmond, Washington. Her research interests are Spectral Graph Theory, Algorithms, Complexity, Convex Programming, and Quantum Computing. She is particularly interested in the use of spectral methods in graph algorithms, and more so in developing new spectral techniques that use the full power of graph spectra. She holds the belief that such techniques will help shed light into various unanswered complexity questions, like the Unique Games Conjecture.