13 citations · 38 across the 29 of their papers we have counts for
40 papers
The Two-Dimensional Majority Rule is P-Complete
Pedro Montealegre, Martín Ríos-Wilson
We prove that prediction for the synchronous two-dimensional majority rule is -complete under logspace many-one reductions, resolving a problem open for almost three de…
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…
On the complexity of freezing automata networks of bounded pathwidth
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson +1
An automata network is a graph of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network'…
Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
Pablo Concha-Vega, Eric Goles, Pedro Montealegre +1
In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states , where the local interactions…
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…
Strong and Hiding Distributed Certification of Bipartiteness
Benjamin Jauregui, Augusto Modanese, Pedro Montealegre +1
In this paper, we study the problem of certifying whether a graph is bipartite (i.e. -colorable) with a locally checkable proof (LCP) that is able to hide a -coloring from th…