Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations
Bernhard Haeupler, Marc Kaufmann, Raghu Raman Ravi +1
This paper presents gossip algorithms for aggregation tasks that demonstrate both robustness to adversarial corruptions of any order of magnitude and optimality across a substantia…
cs.DS2024
Bidirectional Dijkstra's Algorithm is Instance-Optimal
Bernhard Haeupler, Richard Hladík, Vaclav Rozhon +2
Although Dijkstra's algorithm has near-optimal time complexity for the problem of finding a shortest path from a given vertex to a given vertex , in practice other algorithm…