<div dir="ltr"><div class="gmail_default"><div class="gmail_default"><div class="gmail_default"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Wednesday, January 19th at<b> <span style="background-color:rgb(255,255,0)">11:30 am CT</span></b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>    </font></font><font color="#000000">Zoom Virtual Talk (</font><font color="#0000ff"><b><a href="https://uchicagogroup.zoom.us/webinar/register/WN_Gd2O68MpQKaYWFD-8aZS4Q" target="_blank">register in advance here</a></b></font><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>Who: </b> </font><font color="#500050">     </font></font></font>Gramoz Goranci, University of Glasgow<font color="#500050">  </font><font color="#000000">  </font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b><font face="arial, sans-serif"><br></font></b></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="font-family:arial,sans-serif;color:rgb(0,0,0)">Title:</b><span style="font-family:arial,sans-serif;color:rgb(0,0,0)">       </span><span style="font-family:arial,sans-serif">Novel Algorithmic Frameworks for Dynamic Problems on Graphs</span><br></p><div style="color:rgb(0,0,0)"><span style="color:rgb(34,34,34)"><b><font face="arial, sans-serif"><br></font></b></span></div><div style="color:rgb(0,0,0)"><span style="color:rgb(34,34,34)"><b><font face="arial, sans-serif">Abstract: </font></b></span><span style="font-family:arial,sans-serif;color:rgb(34,34,34)">With the emergence of large data sets and the need to understand them, there has been an ever-growing interest in the design and analysis of fast algorithms. In classic algorithm design, the input data is revealed upfront, and the goal is to design algorithms that run in time close to linear with respect to the input size. However, in my real-world graph mining applications such as routing in road networks, robustness detection in communication networks, and community discovery in social networks, data is subject to frequent changes. This motivates the study of dynamic graph algorithms; data structures that maintain relevant graph information under edge/vertex updates while avoiding recomputations from scratch after each update.</span><br></div><div style="color:rgb(0,0,0)"><span style="color:rgb(34,34,34)"><font face="arial, sans-serif"><div><br></div>In this talk, I will describe two novel algorithmic frameworks for designing provable dynamic graph algorithms: (i) vertex sparsification and (ii) tree-based graph approximations. I will discuss how to leverage these frameworks in obtaining dynamic Laplacian solvers and maximum flows, as well as their implications in the context of speeding up or derandomizing core combinatorial optimization problems including maximum flow, minimum cost flow, and global minimum cut. Finally, I’ll talk about open problems and future work.<br></font></span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p></div><div class="gmail_default"><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:yury@ttic.edu" target="_blank"><b>Yury Makarychev</b></a></font></div></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div></div><div><div dir="ltr" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>