gramoz.goranci@univie.ac.at
Office: 6.32
University of Vienna
Gramoz Goranci
Währinger Str. 29
1090 Vienna
Austria
Gramoz Goranci
About me:
I'm an assistant professor (tenure-track) of algorithms at the University of Vienna. I'm a member of the Research Group Theory and Applications of Algorithms. Prior to that, I was an advanced fellow in the Institute for Theoretical Studies, ETH Zürich, held a lectureship at the University of Glasgow, and did a PostDoc at CS Theory Group, University of Toronto, working with Sushant Sachdeva. I completed a PhD in Computer Science at the University of Vienna, where I was fortunate to have Monika Henzinger as my adviser (CV).
Research Interests:
I am broadly interested in algorithm design, and its connections to optimization, graph theory, and machine learning. Much of my research has centered around the design of fast dynamic algorithms for classic and novel large-scale optimization problems with both theoretical guarantees and practical efficiency. My work brings together tools from many areas such as combinatorial data structures, algorithmic graph theory, numerical linear algebra, and metric embeddings.
News:
One paper accepted to ITCS 2024: "Electrical Flows for Polylogarithmic Competitive Oblivious Routing".
Two papers accepted to SODA 2024: "Fast Algorithms for Structured Linear Programs" and "Dynamic Algorithms for k-center on Graphs"
I'm a long-term participant at UC Berkeley's Simons Institute program in Data Structures and Optimization for Fast Algorithms
I'm on the program committee of "Scandinavian Symposium on Algorithm Theory (SWAT) 2024".
One paper accepted to ESA 2023: "Bootstrapping Dynamic Distance Oracles".
One paper accepted to ICALP 2023: "Efficient Data Structures for Incremental Exact and Approximate Maximum Flow", extending the paper "Incremental Approximate Maximum Flow in m^{1/2+o(1)} update time".
One paper accepted to SODA 2023: "Fully Dynamic Exact Edge Connectivity in Sublinear Time".
I am on the program committee of ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023.
Two papers accepted to SODA 2022: "Nested Dissection meets IPMs: Planar Min-Cost Flow in Nearly Linear Time" and "Universally-Optimal Distributed Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing".
One paper accepted to FOCS 2021: "Minor Sparsifiers and the Distributed Laplacian Paradigm".
I am on the program committee of European Symposium on Algorithms (ESA) 2022 Track B.
I am on the program committee of SIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2022.
One paper accepted to KDD 2021: "Local Algorithms for Estimating Effective Resistance".
I will give a talk at the DIMAP Seminar, University of Warwick on May 24, 2021.
I will give a talk at the ETH Zurich Algorithms & Complexity Seminar on May 13, 2021.
In April 2021, I gave a (virtual) talk at Google Research (Mountain View).
I will be on the program committee of European Symposium on Algorithms (ESA) 2021 Track A.
New paper on ArXiv: "Minor Sparsifiers and the Distributed Laplacian Paradigm".
Two papers accepted to SODA 2021: "The Expander Hierarchy and its Applications to Dynamic Graph Algorithms" and "Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications".
One paper accepted to ALENEX 2021: "Fully Dynamic k-Center Clustering in Doubling Metrics".
Paper "Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers" was accepted to FOCS 2020.
The paper "Faster Graph Embeddings via Coarsening" was accepted to ICML 2020.
I gave a keynote talk at the AlgPie by IGAFIT workshop in October 2019.
Two papers I co-authored were accepted to STOC 2019.
Publications
Fully Dynamic Exact Edge Connectivity in Sublinear Time [pdf] (with Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen)
In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023
Nested Dissection meets IPMs: Planar Min-Cost Flow in Nearly Linear Time [pdf] (with Sally Dong, Yu Gao, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Guanghao Ye)
In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing [pdf] (with Bernhard Haeupler, Xiaorui Sun, Mingquan Ye, Goran Zuzic)
In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022
Minor Sparsifiers and the Distributed Laplacian Paradigm [pdf] (with Sebastian Forster, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye)
In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2021
Local Algorithms for Estimating Effective Resistance [pdf] (with Daniel Lopatta, Pan Peng, Yuichi Yoshida)
In Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2021
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms [pdf] (with Harald Räcke , Thatchaphol Saranurak, Zihan Tan)
In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications [pdf] (with Sebastian Forster, Monika Henzinger)
In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021
Fully Dynamic k-Center Clustering in Doubling Metrics [pdf] (with Monika Henzinger, Dariusz Leniowski, Christian Schulz, Alexander Svozil)
In Proceedings of the 14th SIAM Symposium on Algorithm Engineering and Experimentation (ALENEX), 2021
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers [pdf] (with Li Chen, Monika Henzinger, Richard Peng, Thatchaphol Saranurak)
In Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS), 2020
Faster Graph Embeddings via Coarsening [pdf] (with Matthew Fahrbach, Richard Peng, Sushant Sachdeva and Chi Wang)
In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020
Fully Dynamic Vertex Spectral Sparsifiers and Applications [pdf] (with David Durfee, Yu Gao, Richard Peng)
In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 2019
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions [pdf] (with Sebastian Forster)
In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 2019
A Tree Structure For Dynamic Facility Location [pdf] (with Monika Henzinger, Dariusz Leniowski )
In Proceedings of the 26th European Symposium on Algorithms (ESA), 2018
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs [pdf] (with Monika Henzinger, Pan Peng)
In Proceedings of the 26th European Symposium on Algorithms (ESA), 2018
Improved Guarantees for Vertex Sparsification in Planar Graphs [pdf] (with Monika Henzinger, Pan Peng)
SIAM Journal on Discrete Mathematics (SIDMA), Volume 34 Issue 1, pp. 130-162, 2020
In Proceedings of the 25th European Symposium on Algorithms (ESA), 2017
The Power of Vertex Sparsifiers in Dynamic Graph Algorithms [pdf] (with Monika Henzinger, Pan Peng)
In Proceedings of the 25th European Symposium on Algorithms (ESA), 2017
Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time [pdf] (with Monika Henzinger, Mikkel Thorup)
ACM Transaction on Algorithms (TALG), Volume 14 Issue 2, Article No. 17, 2018
In Proceedings of the 24th European Symposium on Algorithms (ESA), 2016.
Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds [pdf] (with Yun Kuen Cheung, Monika Henzinger)
In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 2016.
Vertex Sparsification in Trees [pdf] (with Harald Räcke)
In Proceedings of the 14th Workshop on Approximation and Online Algorithms (WAOA), 2016.
Teaching
Distributed and Parallel Algorithms, Instructor, Summer 2023, University of Vienna
Algorithms and Data Structures 2, Instructor, Summer 2023, University of Vienna
COMPSCI2001 Java Programming 2, Instructor, Fall 2021, University of Glasgow
CSC373 Algorithm Design and Analysis, Instructor, Fall 2020, University of Toronto Mississauga
Mathematical Foundations of Computer Science 1, Teaching Assistant, WS16, SS17, WS18, SS19, WS 19 University of Vienna
Introduction to Theoretical Computer Science, Teaching Assistant, SS16, University of Vienna