CSL Master Calendar

Back to Listing

DCL Lecture Series: Alexandra Kolla, "Exact Algorithms for Semi-Random k-Clustering"

Event Type
Seminar/Symposium
Sponsor
Decision and Control Laboratory, Coordinated Science Laboratory
Location
CSL Auditorium BO2
Date
Feb 18, 2015   3:00 - 4:00 pm  
Speaker
Assistant Professor Alexandra Kolla, Computer Science, UIUC
Cost
No Cost
Contact
Heather Glanzer
E-Mail
hglanzer@illinois.edu
Phone
217/333/0433
Views
78
Originating Calendar
CSL Decision and Control Group

Title:  Exact Algorithms for Semi-Random k-Clustering

Abstract:

 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.

 Biography:

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.

link for robots only