3 papers
cs.DC2026
Contention Resolution, With and Without a Global Clock
Zixi Cai, Kuowen Chen, Shengquan Du +3
In the Contention Resolution problem parties each wish to have exclusive use of a shared resource for one unit of time. The problem has been studied since the early 1970s, unde…
cs.DS2025
Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
Noam Horowicz, Tsvi Kopelowitz
In the snippets problem, the goal is to preprocess text so that given two patterns and , one can locate the occurrences of the two patterns in that are closest t…
cs.DS2024
On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
Tsvi Kopelowitz, Ariel Korin, Liam Roditty
For an undirected unweighted graph G = (V, E) with n vertices and m edges, let d(u, v) denote the distance from u in V to v in V in G. An (alpha, beta)-stretch approximate distance…