<div dir="ltr"><div><font style="color:rgb(0,0,0);font-family:arial,sans-serif"><b>When:</b>     Friday, January 10th.  <b>Refreshments at 12:00pm. </b></font><b>Talk at 12:20pm. *Please note updated time*</b></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><span style="font-family:arial,helvetica,sans-serif"><b>Where:</b>    </span><span style="font-family:arial,helvetica,sans-serif">TTIC</span><span style="font-family:arial,helvetica,sans-serif">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><div><p style="margin-bottom:0.0001pt;line-height:normal"><font face="arial, helvetica, sans-serif"><b>Who: </b>     <b> </b></font>Thatchaphol Saranurak, TTIC</p><table cellpadding="0" style="border-collapse:collapse;margin-top:0px;width:auto;font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:0.875rem;letter-spacing:0.2px;display:block"></table></div><div><br></div><div><b>Title:        </b><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">Algorithmic Paradigms for Dynamic Graphs</span></div><div><br></div><div><b>Abstract:</b> <span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">Dynamic graph algorithms maintain some information about graphs that undergo edge/vertex updates without recomputing everything from scratch after each update. These algorithms have promising applications both in practice and in theory. However, it remains very challenging whether there exist fast dynamic algorithms even for basic graph information such as connectivity, shortest paths, matching, etc.    </span></div><div style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">I will talk about two general techniques that can be used to improve the state-of-the-art of many dynamic graph algorithms: 1) dynamic expander decomposition and 2) local clustering.</div><div style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">These techniques developed for dynamic graphs, in turn, lead to exciting applications even in the classic static setting. </div><div style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">For example, they break the 50-year-old quadratic time bound for checking k-vertex-connectivity to near-linear time.</div><div style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif"><br></div></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><div style="font-size:13px;margin:0px;line-height:normal"><b style="font-size:12.8px"><font face="arial, helvetica, sans-serif">******************************************************************************************************</font></b><br></div><div style="font-family:arial;font-size:13px;margin:0px;line-height:normal"><div style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif">Research at TTIC Seminar Series</font></b></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended both for students seeking research topics and adviser, and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" target="_blank" style="font-family:arial,sans-serif;text-decoration-line:none">https://groups.google.com/a/ttic.edu/group/talks/subscribe</a></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" target="_blank" style="font-family:arial,sans-serif;text-decoration-line:none">http://www.ttic.edu/tticseminar.php</a>.</font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" target="_blank" style="font-family:arial,sans-serif;text-decoration-line:none">nati@ttic.edu</a>.</font></div></div></div><div class="gmail-yj6qo gmail-ajU" style="outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br class="gmail-Apple-interchange-newline"></div><div><br></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave., </i></font><i style="color:rgb(11,83,148)">Office 504</i></div><div><i style="color:rgb(11,83,148)">Chicago, IL 60637</i><br></div></div><div><i style="color:rgb(11,83,148)">773-834-3321</i><i style="color:rgb(11,83,148)"><br></i></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div></div></div></div>