Pedro Montealegre

98 papers A* 6A 4B 14C 2Journal 67Unranked 5
YearRankTypeTitle / Venue / Authors
2026 J jnl
Complexity of the freezing majority rule with L-shaped neighborhoods.
Theor. Comput. Sci.
Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot
2026 J jnl
Distributed Model Checking on Graphs of Bounded Treedepth.
Algorithmica
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2026 J jnl
On the complexity of freezing automata networks of bounded pathwidth.
Nat. Comput.
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier
2025 A* conf
Brief Announcement: Deciding FO Formulas Efficiently in Congested Networks.
PODC
Fedor V. Fomin, Pierre Fraigniaud, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2025 A* conf
Brief Announcement: Strong and Hiding Distributed Certification of
PODC
Augusto Modanese, Pedro Montealegre, Martín Ríos-Wilson
2025 J jnl
Compact distributed certification of geometric graph classes.
J. Comput. Syst. Sci.
Benjamin Jauregui, Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
2025 J jnl
Complexity of the Freezing Majority Rule with L-shaped Neighborhoods.
CoRR
Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot
2025 A* conf
Deterministic Distributed DFS via Cycle Separators in Planar Graphs.
PODC
Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport
2025 J jnl
Dynamical stability of threshold networks over undirected signed graphs.
Theor. Comput. Sci.
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Sylvain Sené
2025 J jnl
On the complexity of freezing automata networks of bounded pathwidth.
CoRR
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier
2025 B conf
Recognizing Hereditary Properties in the Presence of Byzantine Nodes.
OPODIS
David Cifuentes-Núñez, Pedro Montealegre, Ivan Rapaport
2025 J jnl
Sandpiles prediction and crossover on $\mathbb {Z}^2$ within Moore neighborhood.
Nat. Comput.
Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot
2025 J jnl
Shared Versus Private Randomness in Distributed Interactive Proofs.
Algorithmica
Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
2024 J jnl
A Meta-Theorem for Distributed Certification.
Algorithmica
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2024 A* conf
Brief Announcement: Distributed Model Checking on Graphs of Bounded Treedepth.
PODC
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2024 J jnl
Distributed Model Checking in Graphs Classes of Bounded Expansion.
CoRR
Fedor V. Fomin, Pierre Fraigniaud, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2024 A conf
Distributed Model Checking on Graphs of Bounded Treedepth.
DISC
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2024 J jnl
Distributed Model Checking on Graphs of Bounded Treedepth.
CoRR
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2024 B conf
Local Certification of Majority Dynamics.
SOFSEM
Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier
2024 J jnl
On the parameterized complexity of freezing dynamics.
Adv. Appl. Math.
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier
2024 — conf
The Hardness of Local Certification of Finite-State Dynamics.
LATIN (1)
Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson
2023 A conf
Distributed Certification for Classes of Dense Graphs.
DISC
Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2023 J jnl
Distributed Certification for Classes of Dense Graphs.
CoRR
Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2023 J jnl
Distributed maximal independent set computation driven by finite-state dynamics.
Int. J. Parallel Emergent Distributed Syst.
Eric Goles, Laura Leal, Pedro Montealegre, Ivan Rapaport, Martín Ríos-Wilson
2023 J jnl
Dynamical Stability of Threshold Networks over Undirected Signed Graphs.
CoRR
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Sylvain Sené
2023 B conf
Energy-Efficient Distributed Algorithms for Synchronous Networks.
SIROCCO
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2023 J jnl
Energy-Efficient Distributed Algorithms for Synchronous Networks.
CoRR
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2023 J jnl
Local Certification of Majority Dynamics.
CoRR
Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier
2023 J jnl
Local Certification of Some Geometric Intersection Graph Classes.
CoRR
Benjamin Jauregui, Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
2023 J jnl
Local certification of graphs with bounded genus.
Discret. Appl. Math.
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, Ioan Todinca
2023 J jnl
Recognizing Hereditary Properties in the Presence of Byzantine Nodes.
CoRR
David Cifuentes-Núñez, Pedro Montealegre, Ivan Rapaport
2023 J jnl
Symmetrizable Boolean networks.
Inf. Sci.
Juan A. Aledo, Eric Goles, Marco Montalva-Medel, Pedro Montealegre, José C. Valverde
2023 J jnl
The Hardness of Local Certification of Finite-State Dynamics.
CoRR
Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson
2022 B conf
A Meta-Theorem for Distributed Certification.
SIROCCO
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2022 A conf
Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks.
DISC
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, Ioan Todinca
2022 J jnl
Computational Complexity of Biased Diffusion-Limited Aggregation.
SIAM J. Discret. Math.
Nicolas Bitar, Eric Goles, Pedro Montealegre
2022 B conf
Computing Power of Hybrid Models in Synchronous Networks.
OPODIS
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, Ioan Todinca
2022 J jnl
Computing Power of Hybrid Models in Synchronous Networks.
CoRR
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, Ioan Todinca
2022 — conf
Computing the Probability of Getting Infected: On the Counting Complexity of Bootstrap Percolation.
Automata and Complexity
Pedro Montealegre, Martín Ríos-Wilson
2022 B conf
Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes.
SIROCCO
Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport
2022 J jnl
On the complexity of generalized Q2R automaton.
Adv. Appl. Math.
Eric Goles, Marco Montalva-Medel, Pedro Montealegre, Martín Ríos-Wilson
2021 J jnl
A Meta-Theorem for Distributed Certification.
CoRR
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2021 J jnl
Compact Distributed Certification of Planar Graphs.
Algorithmica
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, Ioan Todinca
2021 C conf
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs.
SSS
Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
2021 J jnl
Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes.
CoRR
Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport
2021 J jnl
Freezing sandpiles and Boolean threshold networks: Equivalence and complexity.
Adv. Appl. Math.
Eric Goles, Pedro Montealegre, Kévin Perrot
2021 J jnl
Freezing sandpiles and Boolean threshold networks: equivalence and complexity.
CoRR
Eric Goles, Pedro Montealegre, Kévin Perrot
2021 J jnl
Generating Boolean Functions on Totalistic Automata Networks.
CoRR
Eric Goles, Andrew Adamatzky, Pedro Montealegre, Martín Ríos-Wilson
2021 J jnl
Generating Boolean Functions on Totalistic Automata Networks.
Int. J. Unconv. Comput.
Eric Goles, Andrew Adamatzky, Pedro Montealegre, Martín Ríos-Wilson
2021 C conf
On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics.
CiE
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier
2021 J jnl
On the complexity of asynchronous freezing cellular automata.
Inf. Comput.
Eric Goles, Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson
2021 J jnl
On the complexity of the generalized Q2R automaton.
CoRR
Eric Goles Ch., Marco Montalva-Medel, Pedro Montealegre, Martín Ríos-Wilson
2021 J jnl
The role of randomness in the broadcast congested clique model.
Inf. Comput.
Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2020 A* conf
Compact Distributed Certification of Planar Graphs.
PODC
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, Ioan Todinca
2020 J jnl
Compact Distributed Certification of Planar Graphs.
CoRR
Laurent Feuilloley, Pierre Fraigniaud, Ivan Rapaport, Eric Rémila, Pedro Montealegre, Ioan Todinca
2020 J jnl
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs.
CoRR
Pedro Montealegre, Diego Ramírez-Romero, Iván Rapaport
2020 J jnl
Computational Complexity of the Stability Problem for Elementary Cellular Automata.
J. Cell. Autom.
Eric Goles, Fabiola Lobos, Pedro Montealegre, Eurico L. P. Ruivo, Pedro P. B. de Oliveira
2020 J jnl
Finding connected secluded subgraphs.
J. Comput. Syst. Sci.
Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, Pedro Montealegre
2020 J jnl
Graph reconstruction in the congested clique.
J. Comput. Syst. Sci.
Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport, Ioan Todinca
2020 J jnl
Local Certification of Graphs with Bounded Genus.
CoRR
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Eric Rémila, Ioan Todinca
2020 J jnl
On the complexity of the stability problem of binary freezing totalistic cellular automata.
Inf. Comput.
Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger
2020 J jnl
On the impact of treewidth in the computational complexity of freezing dynamics.
CoRR
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier
2020 B conf
Shared vs Private Randomness in Distributed Interactive Proofs.
ISAAC
Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
2020 J jnl
Shared vs Private Randomness in Distributed Interactive Proofs.
CoRR
Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
2020 J jnl
The Impact of Locality in the Broadcast Congested Clique Model.
SIAM J. Discret. Math.
Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2020 J jnl
The complexity of the asynchronous prediction of the majority automata.
Inf. Comput.
Eric Goles, Pedro Montealegre
2019 J jnl
Beyond Classes of Graphs with "Few" Minimal Separators: FPT Results Through Potential Maximal Cliques.
Algorithmica
Mathieu Liedloff, Pedro Montealegre, Ioan Todinca
2019 J jnl
Computational Complexity of Restricted Diffusion Limited Aggregation.
CoRR
Nicolas Bitar, Eric Goles, Pedro Montealegre
2019 B conf
On Distributed Merlin-Arthur Decision Protocols.
SIROCCO
Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, Ioan Todinca
2019 J jnl
On the Complexity of Asynchronous Freezing Cellular Automata.
CoRR
Eric Goles, Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson
2019 J jnl
On the Complexity of the Stability Problem of Binary Freezing Totalistic Cellular Automata.
CoRR
Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger
2019 — conf
On the Effects of Firing Memory in the Dynamics of Conjunctive Networks.
Automata
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson
2019 J jnl
On the effects of firing memory in the dynamics of conjunctive networks.
CoRR
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson
2018 J jnl
A Mining a Class of Decision Problems for One-dimensional Cellular Automata.
J. Cell. Autom.
Fabiola Lobos, Eric Goles, Eurico L. P. Ruivo, Pedro Paulo Balbi de Oliveira, Pedro Montealegre
2018 J jnl
Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques.
Algorithmica
Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca
2018 J jnl
Fixing improper colorings of graphs.
Theor. Comput. Sci.
Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff, Pedro Montealegre, Pawel Rzazewski
2018 J jnl
On the complexity of two-dimensional signed majority cellular automata.
J. Comput. Syst. Sci.
Eric Goles, Pedro Montealegre, Kévin Perrot, Guillaume Theyssier
2018 B conf
The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model.
LATIN
Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
2018 B conf
Two Rounds Are Enough for Reconstructing Any Graph (Class) in the Congested Clique Model.
SIROCCO
Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport, Ioan Todinca
2017 J jnl
Distributed Subgraph Detection.
CoRR
Pierre Fraigniaud, Pedro Montealegre, Dennis Olivetti, Ivan Rapaport, Ioan Todinca
2017 B conf
Finding Connected Secluded Subgraphs.
IPEC
Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, Pedro Montealegre
2017 J jnl
Finding Connected Secluded Subgraphs.
CoRR
Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, Pedro Montealegre
2017 J jnl
Graph Reconstruction in the Congested Clique.
CoRR
Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport, Ioan Todinca
2017 — conf
On the Computational Complexity of the Freezing Non-strict Majority Automata.
AUTOMATA
Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger
2017 A conf
Three Notes on Distributed Property Testing.
DISC
Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, Ioan Todinca
2016 — conf
A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton.
ACRI
Eric Goles, Pedro Montealegre
2016 A* conf
Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique.
PODC
Pedro Montealegre, Ioan Todinca
2016 J jnl
Deterministic graph connectivity in the broadcast congested clique.
CoRR
Pedro Montealegre, Ioan Todinca
2016 J jnl
Fixing improper colorings of graphs.
CoRR
Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff, Pedro Montealegre, Pawel Rzazewski
2016 J jnl
Naming Game Automata Network.
J. Cell. Autom.
Eric Goles, Pedro Montealegre, Javier Vera
2016 B conf
On Distance-d Independent Set and Other Problems in Graphs with "few" Minimal Separators.
WG
Pedro Montealegre, Ioan Todinca
2016 J jnl
On Distance-d Independent Set and other problems in graphs with few minimal separators.
CoRR
Pedro Montealegre, Ioan Todinca
2016 J jnl
PSPACE-completeness of majority automata networks.
Theor. Comput. Sci.
Eric Goles, Pedro Montealegre, Ville Salo, Ilkka Törmä
2015 B conf
Beyond Classes of Graphs with "Few" Minimal Separators: FPT Results Through Potential Maximal Cliques.
WG
Mathieu Liedloff, Pedro Montealegre, Ioan Todinca
2015 J jnl
PSPACE-Completeness of Majority Automata Networks.
CoRR
Eric Goles Ch., Pedro Montealegre, Ville Salo, Ilkka Törmä
2015 J jnl
The complexity of the majority rule on planar graphs.
Adv. Appl. Math.
Eric Goles, Pedro Montealegre
2014 J jnl
Computational complexity of threshold automata networks under different updating schemes.
Theor. Comput. Sci.
Eric Goles Ch., Pedro Montealegre
2014 B conf
The Simultaneous Number-in-Hand Communication Model for Networks: Private Coins, Public Coins and Determinism.
SIROCCO
Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca