[Colloquium] [Talks at TTIC] *Updated* 1/10 Research at TTIC: Thatchaphol Saranurak, TTIC

[Alicia McClarin]

*When:*     Friday, January 10th.  *Refreshments at 12:00pm. **Talk at
12:20pm. *Please note updated time**

*Where:*    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

*Who: *      Thatchaphol Saranurak, TTIC

*Title:        *Algorithmic Paradigms for Dynamic Graphs

*Abstract:* 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.
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.
These techniques developed for dynamic graphs, in turn, lead to exciting
applications even in the classic static setting.
For example, they break the 50-year-old quadratic time bound for checking
k-vertex-connectivity to near-linear time.

********************************************************************************************************

*Research at TTIC Seminar Series*

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.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>.

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 504*
*Chicago, IL 60637*
*773-834-3321*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20200109/5b1cbf96/attachment.html>