24 citations · 75 across the 13 of their papers we have counts for
22 papers
At the Limits of Computability: Steps Towards Autonomous AI Discovery on the Busy Beaver Frontier
Marco Dos Santos, Vivek Veeriah, Alex Havrilla +4
Recent breakthroughs in AI for mathematics---ranging from Olympiad medal performances to resolving long-standing open conjectures---have rapidly expanded what automated systems can…
Sparse Semi-Oblivious Routing: Few Random Paths Suffice
Goran Zuzic, Bernhard Haeupler, Antti Roeyskoe
The packet routing problem asks to select routing paths that minimize the maximum edge congestion for a set of packets specified by source-destination vertex pairs. We revisit a se…
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň, Bernhard Haeupler, Anders Martinsson +2
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorith…
Universally-Optimal Distributed Exact Min-Cut
Mohsen Ghaffari, Goran Zuzic
We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in rounds on every grap…
Undirected -Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms
Václav Rozhoň, Christoph Grunau, Bernhard Haeupler +2
This paper presents near-optimal deterministic parallel and distributed algorithms for computing -approximate single-source shortest paths in any undirected weight…
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
Goran Zuzic, Gramoz Goranci, Mingquan Ye +2
We provide universally-optimal distributed graph algorithms for -approximate shortest path problems including shortest-path-tree and transshipment. The universal o…
A Simple Boosting Framework for Transshipment
Goran Zuzic
Transshipment, also known under the names of earth mover's distance, uncapacitated min-cost flow, or Wasserstein's metric, is an important and well-studied problem that asks to fin…
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler +2
In this paper, we refine the (almost) \emph{existentially optimal} distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (a…
Universally-Optimal Distributed Algorithms for Known Topologies
Bernhard Haeupler, David Wajc, Goran Zuzic
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do b…
Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic
Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorith…
Tree Embeddings for Hop-Constrained Network Design
Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic
Network design problems aim to compute low-cost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop l…
Hop-Constrained Oblivious Routing
Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic
We prove the existence of an oblivious routing scheme that is -competitive in terms of , thus resolving a well-known question in obl…
Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training
Goran Zuzic, Di Wang, Aranyak Mehta +1
We address the challenge of finding algorithms for online allocation (i.e. bipartite matching) using a machine learning approach. In this paper, we focus on the AdWords problem, wh…
Robust Algorithms for the Secretary Problem
Domagoj Bradac, Anupam Gupta, Sahil Singla +1
In classical secretary problems, a sequence of elements arrive in a uniformly random order, and we want to choose a single item, or a set of size . The random order model al…
Network Coding Gaps for Completion Times of Multiple Unicasts
Bernhard Haeupler, David Wajc, Goran Zuzic
We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to…
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
Domagoj Bradac, Sahil Singla, Goran Zuzic
Consider a kidney-exchange application where we want to find a max-matching in a random graph. To find whether an edge exists, we need to perform an expensive test, in which ca…
Erasure Correction for Noisy Radio Networks
Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz +1
The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. T…
Minor Excluded Network Families Admit Fast Distributed Algorithms
Bernhard Haeupler, Jason Li, Goran Zuzic
Distributed network optimization algorithms, such as minimum spanning tree, minimum cut, and shortest path, are an active research area in distributed computing. This paper present…
Broadcasting in Noisy Radio Networks
Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz +1
The widely-studied radio network model [Chlamtac and Kutten, 1985] is a graph-based description that captures the inherent impact of collisions in wireless communication. In this m…
Fast and simple algorithms for computing both and
Filip Pavetić, Ivan Katanić, Gustav Matula +2
Longest Common Subsequence () deals with the problem of measuring similarity of two strings. While this problem has been analyzed for decades, the recent interest stems from a…
Low-Congestion Shortcuts without Embedding
Bernhard Haeupler, Taisuke Izumi, Goran Zuzic
Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be signi…
++: Practical similarity metric for long strings
Filip Pavetić, Goran Žužić, Mile Šikić
In this paper we present ++: a new metric for measuring the similarity of long strings, and provide an algorithm for its efficient computation. With ever increasing size of s…