Computer Science

Computer Science Seminar: Dr. Alexandra Kolla

Computer Science Seminar: Dr. Alexandra Kolla

Host: Dave Doty

When: Thursday, February 23rd at 3:10pm

Where: 1131 Kemper Hall

Title: “The sound of graphs.”

Abstract: In this talk, I will discuss major implications that linear algebraic techniques have in understanding and resolving hard computational and graph theoretical questions, as well as unifying various areas of mathematics and computer science. I will focus on two representative examples, stemming from two key areas of computer science, namely Computational Complexity and robust Network Design respectively:
(1) Resolving the infamous Unique Games Conjecture and its implications to the theory of inapproximability.
(2) Constructing optimal expander graphs, and its implications to fault tolerant network design and clustering.
I will show how, via the prism of spectral graph theory, those seemingly unrelated questions can be seen to be deeply connected. I will present techniques I developed to tackle both problems, which span a wide range of areas such as linear algebra, convex optimization, group theory, harmonic analysis, and probability theory.
Bio: I am an assistant professor at the Computer Science Department at UIUC. I was a Simons Institute fellow for the academic year 2013-2014. I got my PhD at U.C Berkeley, then did a postdoc at the Institute for Advanced Study and at Microsoft Research. My research focuses on theoretical computer science and specifically spectral graph theory and its applications.

1131 Kemper Hall

Loading Map....