[Theory] 1/19 Talks at TTIC: Gramoz Goranci, University of Glasgow

[Mary Marre]

*When:*     Wednesday, January 19th at* 11:30 am CT*



*Where:*    Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_Gd2O68MpQKaYWFD-8aZS4Q>*)


*Who: *      Gramoz Goranci, University of Glasgow



*Title:*       Novel Algorithmic Frameworks for Dynamic Problems on Graphs

*Abstract: *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.

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.


*Host*: *Yury Makarychev* <yury at ttic.edu>



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220113/8673fa04/attachment-0001.html>