CS Special Seminar: Gramoz Goranci "Novel Algorithmic Frameworks for Dynamic Problems on Graphs"

Novel Algorithmic Frameworks for Dynamic Problems on Graphs

Gramoz Goranci
University of Glasgow
Homepage

Friday, 18 March at 10:15
via Zoom: request the link by email [email protected]
Note! the link will be sent by email to CS staff.

Abstract: In the era of big data, there has been an ever-growing interest in designing fast algorithms. In classic algorithm design, the input data is revealed upfront, and the goal is to design algorithms that run in near-linear time. However, in many real-world applications involving graphs, the input is subject to frequent changes. This motivates the study of dynamic graph algorithms; data structures that maintain relevant graph information under vertex/edge updates.

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 improving the runtime or derandomization of core combinatorial optimization problems such as maximum flow, minimum cost flow, and global minimum cut. Finally, I’ll talk about open problems and future work.

Bio: Gramoz Goranci is a Lecturer (Assistant Professor) at University of Glasgow. He was a postdoc at University of Toronto, and obtained his PhD from University of Vienna in 2019 under the supervision of Monika Henzinger. He is broadly interested in the design and analysis of fast graph algorithms with a focus on dynamic algorithms and compression techniques. His research draws connections between different areas such as combinatorial data structures, graph partitioning, numerical linear algebra, metric embeddings, and machine learning.