Stats, Optimization, and Machine Learning Seminar - Alexandra Kolla

Alexandra Kolla, Assistant Professor of Computer Science, University of Illinois Urbana-Champaign

The Sound of Graphs
 

In this talk, Kolla 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. She will focus on two representative examples, stemming from two key areas of computer science, namely computational complexity and robust network design respectively:

. Resolving the infamous Unique Games Conjecture and its implications to the theory of inapproximability.

. Constructing optimal expander graphs, and its implications to fault tolerant network design and clustering.

Kolla will show how, via the prism of spectral graph theory, those seemingly unrelated questions can be seen to be deeply connected. She will present techniques she 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: Alexandra Kolla is an assistant professor at the Computer Science Department at the University of Illinois Urbana-Champaign. She was a Simons Institute fellow for the academic year 2013-2014. She got her PhD at the University of California Berkeley, then did a postdoc at the Institute for Advanced Study and at Microsoft Research. Her research focuses on theoretical computer science and specifically spectral graph theory and its applications.