13 citations · 38 across the 29 of their papers we have counts for
5 papers · 1 filter
Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes
Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport
A graph is a geometric intersection graph if every node is identified with a geometric object of some particular type, and two nodes are adjacent if the corresp…
A Meta-Theorem for Distributed Certification
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport +1
Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respec…
On the complexity of the generalized Q2R automaton
Eric Goles, Marco Montalva-Medel, Pedro Montealegre +1
We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous upda…
Generating Boolean Functions on Totalistic Automata Networks
Eric Goles, Andrew Adamatzky, Pedro Montealegre +1
We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two…
Freezing sandpiles and Boolean threshold networks: equivalence and complexity
Eric Goles, Pedro Montealegre Kévin Perrot
The NC versus P-hard classification of the prediction problem for sandpiles on the two dimensional grid with von Neumann neighborhood is a famous open problem. In this paper we mak…