### Office: Room S172

School of Computing Science

Sir Alwyn Williams Building

University of Glasgow

Glasgow G12 8RZ

gramoz.goranci AT glasgow.ac.uk

## Gramoz Goranci

**About me:**I am a Lecturer (Assistant Professor) in the School of Computing Science, University of Glasgow. I am a member of the Formal Analysis, Theory and Algorithms (FATA) research section.

I was 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 in 2019, where I was fortunate to have Monika Henzinger as my adviser. Prior to that, I obtained my master's degree under the supervision of Harald Räcke at the Technical Universty of Munich.

From January until April 2018, I was a visiting researcher with Richard Peng at the Georgia Institute of Technology (supported by the Marshall Plan Foundation). (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: **

I am on the program committee of

**ACM-SIAM Symposium on Discrete Algorithms**(**SODA**) 2023.Two papers accepted to

**SODA 202****2**: "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**Two papers I co-authored were accepted to

**STOC 2019**.

## Publications

**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

In Proceedings of the 26th European Symposium on Algorithms (**ESA**), 2018

**Improved Guarantees for Vertex Sparsification in Planar Graphs****[****pdf****]**(with

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

In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (**ICALP**), 2016.

**Vertex Sparsification in Trees****[****pdf****]**(with

In Proceedings of the 14th Workshop on Approximation and Online Algorithms (**WAOA**), 2016.

## Teaching

**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