3 papers
cs.DC2026
Deterministic Distributed DFS and Other Problems via Cycle Separators in Planar Graphs
Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport
One of the most basic techniques in algorithm design consists of breaking a problem into subproblems and then proceeding recursively. In the case of graph algorithms, one way to im…
cs.DS2026
What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud +5
The question of 'what can be computed locally?' lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993), this ques…
cs.DC2025
Recognizing Hereditary Properties in the Presence of Byzantine Nodes
David Cifuentes-Núñez, Pedro Montealegre, Ivan Rapaport
Augustine et al. [DISC 2022] initiated the study of distributed graph algorithms in the presence of Byzantine nodes in the congested clique model. In this model, there is a set …