Events Calendar

CS Colloq: Alexandra Kolla

Talk Title: New Techniques for Using and Approximating Graph SpectraSpeaker: Dr. Alexandra Kolla Host: Prof. David KempeAbstract:
In this talk, we present novel techniques, based on spectral graph theory, and how they are used to design efficient algorithms for both practical and theoretical problems.
In the first part of the talk, we present new techniques for approximating a large graph with a smaller one. Namely, we show how, given a large graph G and a subgraph H of it, we can choose a very small number of edges H' out of H such that replacing H with H' does not change the spectrum of G by much.
We discuss significant implications of our techniques in two interesting practical problems: creating cost-efficient, well-connected networks and speeding up linear system solvers.
In the second part of the talk we present how spectral techniques can be useful for investigating the validity of Khot's Unique Games conjecture (UGC). UGC is one of the most central open problems in computational complexity theory. It asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small.
Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard problems such as Vertex Cover, MaxCut.
We discuss a novel spectral algorithm for deciding satisfiability of Unique Games. We show that our spectral approach works well on instances that previous techniques -which were solely based on linear and semidefinite
programming- provably fail.Bio:
I got my PhD at U.C Berkeley. My advisor was Umesh Vazirani. I am a postdoc at the Institute for Advanced Study in Princeton. My main area of interest is Theory of Computer Science and in particular spectral graph theory, convex programming and their implications to efficient algorithmic design. I am also interested in quantum computing and cryptography.
Bio: TBA

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Front Desk