<div dir="ltr"><div style="font-size:12.8px"><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif">When:     Wednesday, January 10th <span class="gmail-il">at</span> <b style="background-color:rgb(255,255,0)">10:30 am </b></font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif">Where:    <span class="gmail-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"><span class="gmail-il">TTIC</span></span>, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div><font color="#000000"><font face="arial, helvetica, sans-serif">Who:       </font><span style="font-family:arial,helvetica,sans-serif;font-size:small">Thatchaphol Saranurak, </span><span style="font-size:14px"><font face="arial, helvetica, sans-serif" style="">KTH Royal Institute of Technology</font></span></font></div><div><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div></div><font color="#000000"><span style="font-size:12.8px"></span></font><div style="font-size:12.8px"><font color="#000000">Title:        Dynamic Spanning Forest: Techniques and Connections to Other Fields</font><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract: I will first give an overview of dynamic algorithms and their connections to other fields. Then, I will present our recent progress on the question "is there a dynamic algorithm with small worst-case update time" for the spanning forest problem, which is among central problems in dynamic algorithms on graphs. Our result guarantees an n^{o(1)} worst-case update time with high probability, where n is the number of nodes. The best worst-case bounds prior to our work are (i) the long-standing O(\sqrt{n}) bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] (which is slightly improved by a O(\sqrt{\log(n)}) factor by [Kejlberg-Rasmussen, Kopelowitz, Pettie, Thorup ESA'16]) and (ii) the polylogarithmic bound of [Kapron, King and Mountjoy SODA'13] which works under an oblivious adversary assumption (our result does not make such assumption). The crucial techniques are about expanders: 1) an algorithm for decomposing a graph into a collection of expanders in near-linear time, and 2) an algorithm for "repairing" the expansion property of an expander after deleting some edges of it. These techniques can be of independent interest.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">This talk is based on results by [Nanongkai, Saranurak and Wulff-Nilsen, FOCS'17], [Nanongkai and Saranurak, STOC'17] and [Wulff-Nilsen, STOC'17].</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Host: <a href="mailto:yury@ttic.edu">Yury Makarychev</a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div><div class="gmail_signature"><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 504</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>