Goran Zuzic

Research Interests

I am broadly interested in theoretical computer science, with a focus on the principles of distributed computing and graph theory. I am most proud of my work on universal optimality which provides a near-complete theoretical answer to the fundamental question of: "how fast can we solve global problems like the shortest path or the minimum spanning tree in a distributed network?" My coauthors and I design distributed algorithms that perfectly (and provably so) adapt to the underlying communication network. This includes quantifying the fundamental speed limits of coordination in a network, as well as matching those limits with ultra-fast algorithms designed with user-friendly tools.

This pursuit has led to uncovering of new connections between distributed computing and many seemingly-unrelated fields of theoretical computer science: including the theory of metric embedding, information theory, parallel graph algorithms, and optimal oblivious packet routing. Notably, these connections have proven to be mutually beneficial and have led to breakthroughs on both sides.

Recently, I became interested in bringing AI advancements to mathematics by working on Alphaproof. Specifically, I was a co-lead on the formalizer network workstream.

Short Biography

Previously, I was a postdoctoctoral scholar at ETH Zürich, in the research group of Prof. Mohsen Ghaffari (now at MIT). I received my Ph.D. from the School of Computer Science at Carnegie Mellon University under the advisorship of Prof. Bernhard Haeupler with the thesis titled Towards Universal Optimality in Distributed Optimization. Earlier, I obtained my B.Sc. and M.Sc. from University of Zagreb under the advisorship of Prof. Mile Šikić. I like competitive programming and playing volleyball.

I am extremely honored to have received the 2021 ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award (see here and here). Earlier, I was also awarded the 2018 DFINITY Scholarship.

Publications (ⓐ = authors sorted alphabetically; ⓒ = sorted by contribution; ⓡ = order randomized)

• Bernhard Haeupler, Shyamal Patel, Antti Röyskö, Cliff Stein, Goran Zuzic. Polylog-Competitive Deterministic Local Routing and Scheduling. ACM Symposium on Theory of Computing (STOC 2024).
• Goran Zuzic. A Simple Boosting Framework for Transshipment. The European Symposium on Algorithms (ESA 2023). (PDF) (Slides)
• Goran Zuzic ⓡ Bernhard Haeupler ⓡ Antti Roeyskoe. Sparse Semi-Oblivious Routing: Few Random Paths Suffice. ACM Symposium on Principles of Distributed Computing (PODC 2023). (PDF)
• Václav Rozhoň ⓡ Bernhard Haeupler ⓡ Anders Martinsson ⓡ Christoph Grunau ⓡ Goran Zuzic. Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. ACM Symposium on Theory of Computing (STOC 2023). (PDF) (Slides)
• Ioannis Anagnostides ⓡ Christoph Lenzen ⓡ Bernhard Haeupler ⓡ Goran Zuzic ⓡ Themis Gouleakis. Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. Regular paper at the International Symposium on Distributed Computing. (DISC 2022) Brief Announcement at the ACM Symposium on Principles of Distributed Computing (PODC 2022). (PDF) (Slides)
• Bernhard Haeupler ⓐ D. Ellis Hershkowitz ⓐ Goran Zuzic. Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings The European Symposium on Algorithms (ESA 2022). (PDF)
• Mohsen Ghaffari ⓐ Goran Zuzic. Universally-Optimal Distributed Exact Min-Cut. ACM Symposium on Principles of Distributed Computing (PODC 2022). (PDF)
• Goran Zuzic + Di Wang (equal contrib.) ⓒ Aranyak Mehta ⓒ D. Sivakumar. Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training. ICLR 2022 Workshop on Gamification and Multiagent Solutions. (PDF)
• Václav Rozhoň ⓡ Christoph Grunau ⓡ Bernhard Haeupler ⓡ Goran Zuzic ⓡ Jason Li. Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms. ACM Symposium on Theory of Computing (STOC 2022). (PDF)
• Goran Zuzic ⓡ Goramoz Goranci ⓡ Mingquan Ye ⓡ Bernhard Haeupler ⓡ Xiaorui Sun. Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing. ACM-SIAM Symposium on Discrete Algorithms (SODA 2022). (PDF) (Slides)
• Bernhard Haeupler ⓐ David Wajc ⓐ Goran Zuzic. Universally-Optimal Distributed Algorithms for Known Topologies. ACM Symposium on Theory of Computing (STOC 2021). (PDF) (Slides) (Poster) (Video)
• Mohsen Ghaffari ⓐ Bernhard Haeupler ⓐ Goran Zuzic. Hop-Constrained Oblivious Routing. ACM Symposium on Theory of Computing (STOC 2021). Invited to the SIAM Journal of Computing's STOC'21 special issue. (PDF) (Slides)
• Bernhard Haeupler ⓐ D. Ellis Hershkowitz ⓐ Goran Zuzic. Tree Embeddings for Hop-Constrained Network Design. ACM Symposium on Theory of Computing (STOC 2021). (PDF)
• Bernhard Haepler ⓐ David Wajc ⓐ Goran Zuzic. Network Coding Gaps for Completion Times of Multiple Unicasts. IEEE Symposium on Foundations of Computer Science (FOCS 2020). (PDF) (Video)
• Domagoj Bradac ⓐ Anupam Gupta ⓐ Sahil Singla ⓐ Goran Zuzic. Robust Algorithms for the Secretary Problem. Innovations in Theoretical Computer Science (ITCS 2020). (PDF) (Video)
• Domagoj Bradac ⓐ Sahil Singla ⓐ Goran Zuzic. Optimal Adaptivity Gaps for Constrained Stochastic Probing. International Conference on Randomization and Computation (RANDOM 2019). (PDF) (Slides)
• Keren Censor-Hillel ⓐ Bernhard Haeupler ⓐ D. Ellis Hershkowitz ⓐ Goran Zuzic. Erasure Correction for Noisy Radio Networks. International Symposium on Distributed Computing (DISC 2019). (PDF) (Video)
• Bernhard Haeupler ⓐ Jason Li ⓐ Goran Zuzic. Minor Excluded Network Families Admit Fast Distributed Algorithms. ACM Symposium on Principles of Distributed Computing (PODC 2018). (PDF)
• Keren Censor-Hillel ⓐ Bernhard Haeupler ⓐ D. Ellis Hershkowitz ⓐ Goran Zuzic. Broadcasting in Noisy Radio Networks. ACM Symposium on Principles of Distributed Computing (PODC 2017). (PDF) (Video)
• Bernhard Haeupler ⓐ Taisuke Izumi ⓐ and Goran Zuzic. Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs. International Symposium on Distributed Computing (DISC 2016).
• Bernhard Haeupler ⓐ Taisuke Izumi ⓐ and Goran Zuzic. Low-congestion shortcuts without embedding.
  Conference version: ACM Symposium on Principles of Distributed Computing (PODC 2016).
  Journal version: Distributed Computing (DIST 2020). (PDF) (Video) (Slides)

Contact