Monday, 11 March 2024 @ 14:00–15:00 CET

On-site:

University of Vienna
Seminarraum 9
Kolingasse 14–16
1090 Vienna

Online:

Zoom-Link: https://univienna.zoom.us/j/68154688415?pwd=anBCaXlnZ0ZRZ0R2YkV0U2hMSXdIQT09
Meeting-ID: 681 5468 8415
Passcode: 517043

The Power of Vertex Sparsifiers in Dynamic Algorithms

Modern data analysis requires efficient processing of large-scale graphs and dynamic data sets. However, many problems involving graphs that arise in Machine Learning, Computer Vision, Optimization and Network Analysis are not well understood in the dynamic setting.

In this talk, we present a general algorithmic tool for designing dynamic algorithms known as vertex sparsification, a compression paradigm that reduces large graphs into smaller ones while preserving properties or features of interest. In particular, we will show that data-structure variants of vertex sparsifiers lead to dynamic algorithms for maintaining solutions to graph Laplacian systems. By exploiting the interactions between Interior-Point Methods and dynamic Laplacians, we will also briefly discuss implications such as faster algorithms for the maximum and minimum cost flow problems.

Bio

Gramoz Goranci is a tenure-track assistant professor of algorithms in the Faculty of Computer Science at the University of Vienna, Austria. He has a broad interest in algorithm design and its connections to optimization, graph theory, and machine learning. His recent research has focused on designing fast dynamic algorithms for graph-based optimization problems.

Previously, he was a visiting researcher at the Simons Institute, UC Berkeley, and an advanced fellow at ETH Zurich. He completed his postdoc at the University of Toronto, held a permanent lectureship at the University of Glasgow, and received his PhD from the University of Vienna under Monika Henzinger.