3 papers
cs.DS2025
Streaming Diameter of High-Dimensional Points
Magnús M. Halldórsson, Nicolaos Matsakis, Pavel Veselý
We improve the space bound for streaming approximation of Diameter but also of Farthest Neighbor queries, Minimum Enclosing Ball and its Coreset, in high-dimensional Euclidean spac…
cs.DS2025
Faster Dynamic -Coloring Against Adaptive Adversaries
Maxime Flin, Magnús M. Halldórsson
We consider the problem of maintaining a proper -vertex coloring in a graph on -vertices and maximum degree undergoing edge insertions and deletions. We give a rando…
cs.DC2025
When MIS and Maximal Matching are Easy in the Congested Clique
Keren Censor-Hillel, Tomer Even, Maxime Flin +1
Two of the most fundamental distributed symmetry-breaking problems are that of finding a maximal independent set (MIS) and a maximal matching (MM) in a graph. It is a major open qu…