Pedro Montealegre

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 78

Top Topics

Computational Complexity

Independent Set

Maximal Cliques

Top Venues

Publications

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