[Colloquium] 1/16 Talks at TTIC: Aaron Schild, UC Berkeley

[Mary Marre via Colloquium]

When:     Wednesday, January 16th at *11:00 am*

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Aaron Schild, UC Berkeley


*Title*:       Graph Structure via Gaussian Elimination

*Abstract*:  Graph partitioning has played an important role in theoretical
computer science, particularly in the design of approximation algorithms
and metric embeddings. In this talk, we revisit some of these applications
from the perspective of Gaussian elimination, particularly in the context
of random spanning tree generation and oblivious routing. In the process,
we will see how fundamental tradeoffs in graph partitioning can be overcome
by eliminating vertices from an undirected graph using Gaussian elimination
on the associated Laplacian matrix.

*Host:*  Madhur Tulsiani <madhurt at ttic.edu>



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190109/bee536a1/attachment.html>