Stay Informed:
Baskin Engineering COVID-19 Information and Resources
Campus Roadmap to Recovery
Zoom Links: Zoom Help | Teaching with Zoom | Zoom Quick Guide

The Sound of Graphs

Speaker Name: 
Alexandra Kolla
Speaker Title: 
Associate Professor
Speaker Organization: 
Department of Computer Science
Start Time: 
Monday, March 29, 2021 - 11:00am
End Time: 
Monday, March 29, 2021 - 12:15pm
Via Zoom Link
Luca de Alfaro


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. Moreover, I will exhibit a perhaps surprising connection to statistical physics, which has recently proven key in developing new algorithms. I will present techniques I developed to tackle those questions, which span a wide range of areas such as linear algebra, statistical physics, convex optimization, group theory, harmonic analysis, and probability theory. 


Alexandra Kolla is an associate professor at the Computer Science Department at CU Boulder. Prior to that, I was an assistant professor at UIUC. I was a Simons Institute fellow for the academic year 2013-2014, and I have been an invited long-term Simons Institute visitor since, for several semester long programs. I got my PhD at U.C Berkeley in 2010, 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, statistical physics, quantum computing and their applications.

 Zoom Link:

Event Type: