5 citations · 15 across the 23 of their papers we have counts for
30 papers
On the Limits of Quantum Multiparty Simultaneous Communication
Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a r…
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…
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…
Distributed Model Checking on Graphs of Bounded Treedepth
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre +2
We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowl…
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 …
The Minimum Clique Routing Problem on Cycles
Mariana Escalante, Martín Matamala, Iván Rapaport +2
In the Minimum Clique Routing Problem on Cycles \textsc{MCRPC} we are given a cycle together with a set of demands (weighted origin-destination pairs) and the goal is to route all…