<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">When:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">    Friday, February 26th at 11:10am CT</span>  <b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></font></div><div class="gmail_default"><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></div><div class="gmail_default"><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Where:</b><span style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">   </span><span style="font-family:arial,sans-serif;color:rgb(0,0,0)">Zoom Virtual Talk (</span><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font style="color:rgb(26,115,232)"><a href="https://uchicagogroup.zoom.us/j/92324413499?pwd=TU10blNuV09OZWw0UXdzQ3FwVU4yZz09" target="_blank">register in advance here</a>)</font></b><br></div><div class="gmail_default"><b><font face="arial, sans-serif"><br></font></b></div><div class="gmail_default"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Who:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">      Nicole Wein, MIT</span>  <b><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"></b><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></font></div><div class="gmail_default"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></font></div><div class="gmail_default"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Title:     </b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Approximating the Diameter of a Graph</span><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Abstract:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> I will talk about one of the central problems in fine-grained complexity: computing the diameter of a graph (the largest distance between two vertices). The best known algorithm for computing the diameter of a graph is the naive algorithm of computing all-pairs shortest paths (APSP) and taking the largest distance. Moreover, no significantly better algorithm exists under the Strong Exponential Time Hypothesis. Running APSP can be prohibitively slow for very large graphs, so we seek much faster algorithms that produce an </span><i style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">approximation</i><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> of the diameter. I will talk about algorithms and conditional lower bounds for approximating the diameter of a graph. In particular, I will discuss the landscape of time vs. accuracy trade-offs.</span><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Bio:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> Nicole Wein is a final-year PhD student at MIT advised by Virginia Vassilevska Williams. Her research interests are mainly in graph algorithms including dynamic algorithms, parameterized algorithms, data structures, and fine-grained complexity.</span><br clear="all"></font></div><div class="gmail_default"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><br></font></span></div><div class="gmail_default"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a></font></span></div><br class="gmail-Apple-interchange-newline"></div><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"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</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></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Feb 19, 2021 at 6:04 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><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">When:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">    Friday, February 26th at 11:10am CT</span>  <b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></font></div><div><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></div><div><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Where:</b><span style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">   </span><span style="font-family:arial,sans-serif;color:rgb(0,0,0)">Zoom Virtual Talk (</span><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font style="color:rgb(26,115,232)"><a href="https://uchicagogroup.zoom.us/j/92324413499?pwd=TU10blNuV09OZWw0UXdzQ3FwVU4yZz09" target="_blank">register in advance here</a>)</font></b><br></div><div><b><font face="arial, sans-serif"><br></font></b></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Who:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">      Nicole Wein, MIT</span>  <b><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"></b><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></font></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br></b></font></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Title:     </b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Approximating the Diameter of a Graph</span><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Abstract:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> I will talk about one of the central problems in fine-grained complexity: computing the diameter of a graph (the largest distance between two vertices). The best known algorithm for computing the diameter of a graph is the naive algorithm of computing all-pairs shortest paths (APSP) and taking the largest distance. Moreover, no significantly better algorithm exists under the Strong Exponential Time Hypothesis. Running APSP can be prohibitively slow for very large graphs, so we seek much faster algorithms that produce an </span><i style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">approximation</i><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> of the diameter. I will talk about algorithms and conditional lower bounds for approximating the diameter of a graph. In particular, I will discuss the landscape of time vs. accuracy trade-offs.</span><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><br style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Bio:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> Nicole Wein is a final-year PhD student at MIT advised by Virginia Vassilevska Williams. Her research interests are mainly in graph algorithms including dynamic algorithms, parameterized algorithms, data structures, and fine-grained complexity.</span><br clear="all"></font></div><div><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><br></font></span></div><div><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a></font></span></div><div><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><br></font></span></div><div style="font-size:small"><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;font-size:14px;letter-spacing:0.2px;white-space:pre-wrap"><br></span></div><div><div dir="ltr"><div dir="ltr"><div><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">Faculty Administrative Support</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></div></div>
</blockquote></div></div>