Pedro Montealegre-Barba

According to our database, Pedro Montealegre-Barba authored at least 56 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

A Meta-Theorem for Distributed Certification.

Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Algorithmica, February, 2024

Local Certification of Majority Dynamics.

Diego Maldonado, Pedro Montealegre, Martín Ríos Wilson, Guillaume Theyssier

Proceedings of the SOFSEM 2024: Theory and Practice of Computer Science, 2024

The Hardness of Local Certification of Finite-State Dynamics.

Diego Maldonado, Pedro Montealegre, Martín Ríos Wilson

Proceedings of the LATIN 2024: Theoretical Informatics, 2024

2023

Symmetrizable Boolean networks.

Juan A. Aledo, Eric Goles, Marco Montalva-Medel, Pedro Montealegre, José C. Valverde

Inf. Sci., May, 2023

Distributed maximal independent set computation driven by finite-state dynamics.

Eric Goles, Laura Leal, Pedro Montealegre, Ivan Rapaport, Martín Ríos Wilson

Int. J. Parallel Emergent Distributed Syst., 2023

Local certification of graphs with bounded genus.

Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, Ioan Todinca

Discret. Appl. Math., 2023

Recognizing Hereditary Properties in the Presence of Byzantine Nodes.

David Cifuentes-Núñez, Pedro Montealegre, Ivan Rapaport

CoRR, 2023

Local Certification of Some Geometric Intersection Graph Classes.

Benjamin Jauregui, Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport

CoRR, 2023

Dynamical Stability of Threshold Networks over Undirected Signed Graphs.

Eric Goles, Pedro Montealegre, Martín Ríos Wilson, Sylvain Sené

CoRR, 2023

Distributed Certification for Classes of Dense Graphs.

Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Proceedings of the 37th International Symposium on Distributed Computing, 2023

Energy-Efficient Distributed Algorithms for Synchronous Networks.

Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Proceedings of the Structural Information and Communication Complexity, 2023

2022

Computational Complexity of Biased Diffusion-Limited Aggregation.

Nicolas Bitar, Eric Goles, Pedro Montealegre

SIAM J. Discret. Math., 2022

On the complexity of generalized Q2R automaton.

Eric Goles, Marco Montalva-Medel, Pedro Montealegre, Martín Ríos Wilson

Adv. Appl. Math., 2022

Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks.

Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos Wilson, Ioan Todinca

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes.

Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport

Proceedings of the Structural Information and Communication Complexity, 2022

Computing Power of Hybrid Models in Synchronous Networks.

Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos Wilson, Ioan Todinca

Proceedings of the 26th International Conference on Principles of Distributed Systems, 2022

Computing the Probability of Getting Infected: On the Counting Complexity of Bootstrap Percolation.

Pedro Montealegre, Martín Ríos Wilson

Proceedings of the Automata and Complexity, 2022

2021

Generating Boolean Functions on Totalistic Automata Networks.

Eric Goles, Andrew Adamatzky, Pedro Montealegre, Martín Ríos Wilson

Int. J. Unconv. Comput., 2021

On the complexity of asynchronous freezing cellular automata.

Eric Goles, Diego Maldonado, Pedro Montealegre, Martín Ríos Wilson

Inf. Comput., 2021

The role of randomness in the broadcast congested clique model.

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Inf. Comput., 2021

Compact Distributed Certification of Planar Graphs.

Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, Ioan Todinca

Algorithmica, 2021

Freezing sandpiles and Boolean threshold networks: Equivalence and complexity.

Eric Goles, Pedro Montealegre, Kévin Perrot

Adv. Appl. Math., 2021

Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs.

Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2021

On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics.

Eric Goles, Pedro Montealegre, Martín Ríos Wilson, Guillaume Theyssier

Proceedings of the Connecting with Computability, 2021

2020

The Impact of Locality in the Broadcast Congested Clique Model.

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

SIAM J. Discret. Math., 2020

Graph reconstruction in the congested clique.

Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport, Ioan Todinca

J. Comput. Syst. Sci., 2020

Finding connected secluded subgraphs.

Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, Pedro Montealegre

J. Comput. Syst. Sci., 2020

Computational Complexity of the Stability Problem for Elementary Cellular Automata.

Eric Goles, Fabiola Lobos, Pedro Montealegre, Eurico L. P. Ruivo, Pedro P. B. de Oliveira

J. Cell. Autom., 2020

On the complexity of the stability problem of binary freezing totalistic cellular automata.

Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger

Inf. Comput., 2020

The complexity of the asynchronous prediction of the majority automata.

Eric Goles, Pedro Montealegre

Inf. Comput., 2020

Shared vs Private Randomness in Distributed Interactive Proofs.

Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

2019

Computational Complexity of Restricted Diffusion Limited Aggregation.

Nicolas Bitar, Eric Goles, Pedro Montealegre

CoRR, 2019

Beyond Classes of Graphs with "Few" Minimal Separators: FPT Results Through Potential Maximal Cliques.

Mathieu Liedloff, Pedro Montealegre, Ioan Todinca

Algorithmica, 2019

On Distributed Merlin-Arthur Decision Protocols.

Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, Ioan Todinca

Proceedings of the Structural Information and Communication Complexity, 2019

On the Effects of Firing Memory in the Dynamics of Conjunctive Networks.

Eric Goles, Pedro Montealegre, Martín Ríos Wilson

Proceedings of the Cellular Automata and Discrete Complex Systems, 2019

2018

Fixing improper colorings of graphs.

Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff, Pedro Montealegre, Pawel Rzazewski

Theor. Comput. Sci., 2018

On the complexity of two-dimensional signed majority cellular automata.

Eric Goles, Pedro Montealegre, Kévin Perrot, Guillaume Theyssier

J. Comput. Syst. Sci., 2018

A Mining a Class of Decision Problems for One-dimensional Cellular Automata.

Fabiola Lobos, Eric Goles, Eurico L. P. Ruivo, Pedro Paulo Balbi de Oliveira, Pedro Montealegre

J. Cell. Autom., 2018

Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques.

Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca

Algorithmica, 2018

Two Rounds Are Enough for Reconstructing Any Graph (Class) in the Congested Clique Model.

Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport, Ioan Todinca

Proceedings of the Structural Information and Communication Complexity, 2018

The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model.

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata.

Eric Goles, Diego Maldonado, Pedro Montealegre-Barba, Nicolas Ollinger

Proceedings of the Cellular Automata, 2018

2017

Sequential and distributes graph algorithms. Parameterized algorithms via potential maximal cliques; broadcast congested clique. (Algorithmes de graphes séquentiels et distribués. Algorithmes paramétrés via des cliques maximales potentielles ; Modèle de diffusion dans une clique congestionnée).

Pedro Montealegre-Barba

PhD thesis, 2017

Distributed Subgraph Detection.

Pierre Fraigniaud, Pedro Montealegre, Dennis Olivetti, Ivan Rapaport, Ioan Todinca

CoRR, 2017

Three Notes on Distributed Property Testing.

Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, Ioan Todinca

Proceedings of the 31st International Symposium on Distributed Computing, 2017

On the Computational Complexity of the Freezing Non-strict Majority Automata.

Eric Goles, Diego Maldonado, Pedro Montealegre, Nicolas Ollinger

Proceedings of the Cellular Automata and Discrete Complex Systems, 2017

2016

PSPACE-completeness of majority automata networks.

Eric Goles, Pedro Montealegre, Ville Salo, Ilkka Törmä

Theor. Comput. Sci., 2016

Naming Game Automata Network.

Eric Goles, Pedro Montealegre, Javier Vera

J. Cell. Autom., 2016

Deterministic graph connectivity in the broadcast congested clique.

Pedro Montealegre, Ioan Todinca

CoRR, 2016

On Distance-d Independent Set and Other Problems in Graphs with "few" Minimal Separators.

Pedro Montealegre, Ioan Todinca

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique.

Pedro Montealegre, Ioan Todinca

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton.

Eric Goles, Pedro Montealegre

Proceedings of the Cellular Automata, 2016

2015

The complexity of the majority rule on planar graphs.

Eric Goles, Pedro Montealegre

Adv. Appl. Math., 2015

2014

Computational complexity of threshold automata networks under different updating schemes.

Eric Goles Ch., Pedro Montealegre

Theor. Comput. Sci., 2014

The Simultaneous Number-in-Hand Communication Model for Networks: Private Coins, Public Coins and Determinism.

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Proceedings of the Structural Information and Communication Complexity, 2014

2013

The complexity of the bootstraping percolation and other problems.

Eric Goles Ch., Pedro Montealegre-Barba, Ioan Todinca

Theor. Comput. Sci., 2013