<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">When: <span style="font-weight:400">    Wednesday, January 16th </span><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="font-weight:400">at</span><span style="font-weight:400"> </span><b>11:00 am</b></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><br></div><div><font color="#000000" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font face="arial, helvetica, sans-serif">Who:<span style="font-weight:400">       Aaron Schild, UC Berkeley</span></font></font></div><br class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><br class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><b style="font-family:arial,sans-serif;font-size:12.8px">Title</b><span style="font-family:arial,sans-serif;font-size:12.8px">:       </span>Graph Structure via Gaussian Elimination<br>  <br style="font-family:arial,sans-serif;font-size:12.8px"><b style="font-family:arial,sans-serif;font-size:12.8px">Abstract</b><span style="font-family:arial,sans-serif;font-size:12.8px">: </span> 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.<div class="gmail-m_7559459027998801583gmail-yj6qo gmail-m_7559459027998801583gmail-ajU" style="outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><div><div><div><div style="font-family:arial,sans-serif;font-size:12.8px"><b>Host:</b>  <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></div><div style="font-family:arial,sans-serif;font-size:12.8px"><br></div></div></div></div><div dir="ltr"><br></div><div dir="ltr"><br></div><br class="gmail-Apple-interchange-newline"><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr">On Wed, Jan 9, 2019 at 9:38 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">When: <span style="font-weight:400">    Wednesday, January 16th </span><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="font-weight:400">at</span><span style="font-weight:400"> </span><b>11:00 am</b></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><br></div><div><font color="#000000" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font face="arial, helvetica, sans-serif">Who:<span style="font-weight:400">       Aaron Schild, UC Berkeley</span></font></font></div><br class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><br class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><b style="font-family:arial,sans-serif;font-size:12.8px">Title</b><span style="font-family:arial,sans-serif;font-size:12.8px">:       </span>Graph Structure via Gaussian Elimination<br>  <br style="font-family:arial,sans-serif;font-size:12.8px"><b style="font-family:arial,sans-serif;font-size:12.8px">Abstract</b><span style="font-family:arial,sans-serif;font-size:12.8px">: </span>

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.<div class="gmail-m_7559459027998801583gmail-yj6qo gmail-m_7559459027998801583gmail-ajU" style="outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><div><div><div><div style="font-family:arial,sans-serif;font-size:12.8px"><b>Host:</b>  <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></div><div style="font-family:arial,sans-serif;font-size:12.8px"><br></div><br class="gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-Apple-interchange-newline"></div></div></div><br class="gmail-m_7559459027998801583gmail-Apple-interchange-newline"><div><div dir="ltr" class="gmail-m_7559459027998801583gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>