<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><p style="margin:0in 0in 0.0001pt;line-height:normal"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>When</b></font></font></font></font><font style="font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b>:</b>    </font></font><font style="font-family:arial,sans-serif;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></p><div dir="auto"><p style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal"><font face="arial, sans-serif" color="#000000"> </font></p><p style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal"><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 style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal"><font face="arial, sans-serif"><br></font></p><p style="margin:0in 0in 0.0001pt;line-height:normal"><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 style="margin:0in 0in 0.0001pt;line-height:normal"><font face="arial, sans-serif"><br></font></p><p style="margin:0in 0in 0.0001pt;line-height:normal"><b><font face="arial, sans-serif"><br></font></b></p><p style="margin:0in 0in 0.0001pt;line-height:normal"><b style="font-family:arial,sans-serif">Title:</b><span style="font-family:arial,sans-serif">       </span><span style="font-family:arial,sans-serif">Novel Algorithmic Frameworks for Dynamic Problems on Graphs</span><br></p><div><b><font face="arial, sans-serif"><br></font></b></div><div><b><font face="arial, sans-serif">Abstract: </font></b><span style="font-family:arial,sans-serif">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><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></div><p style="margin:0in 0in 0.0001pt;line-height:normal"><font face="arial, sans-serif"><br></font></p></div><div dir="auto"><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 dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div></div><div><div dir="ltr" class="gmail_signature" 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><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jan 18, 2022 at 3:30 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="auto"><div dir="auto"><p style="margin:0in 0in 0.0001pt;line-height:normal"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>When</b></font></font></font></font><font style="font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b>:</b>    </font></font><font style="font-family:arial,sans-serif;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></p><div dir="auto"><p style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal"><font face="arial, sans-serif" color="#000000"> </font></p><p style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal"><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 style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal"><font face="arial, sans-serif"><br></font></p><p style="margin:0in 0in 0.0001pt;line-height:normal"><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 style="margin:0in 0in 0.0001pt;line-height:normal"><font face="arial, sans-serif"><br></font></p><p style="margin:0in 0in 0.0001pt;line-height:normal"><b><font face="arial, sans-serif"><br></font></b></p><p style="margin:0in 0in 0.0001pt;line-height:normal"><b style="font-family:arial,sans-serif">Title:</b><span style="font-family:arial,sans-serif">       </span><span style="font-family:arial,sans-serif">Novel Algorithmic Frameworks for Dynamic Problems on Graphs</span><br></p><div><span style="color:rgb(34,34,34)"><b><font face="arial, sans-serif"><br></font></b></span></div><div><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><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 style="margin:0in 0in 0.0001pt;line-height:normal"><font face="arial, sans-serif"><br></font></p></div><div dir="auto"><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 dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div></div><div style="font-size:small" dir="auto"><br></div><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Thu, Jan 13, 2022, 8:40 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">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><div><div><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" rel="noreferrer" 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><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:yury@ttic.edu" rel="noreferrer" target="_blank"><b>Yury Makarychev</b></a></font></div></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div></div><div><div dir="ltr"><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" rel="noreferrer" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>