
Goles, E., & Montealegre, P. (2020). The complexity of the asynchronous prediction of the majority automata. Inform. Comput., to appear.
Abstract: We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a nonzero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the twodimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NPComplete.



Kiwi, M., de Espanes, P. M., Rapaport, I., Rica, S., & Theyssier, G. (2014). Strict Majority Bootstrap Percolation in the rwheel. Inf. Process. Lett., 114(6), 277–281.
Abstract: In the strict Majority Bootstrap Percolation process each passive vertex v becomes active if at least [deg(v)+1/2] of its neighbors are active (and thereafter never changes its state). We address the problem of finding graphs for which a small proportion of initial active vertices is likely to eventually make all vertices active. We study the problem on a ring of n vertices augmented with a “central” vertex u. Each vertex in the ring, besides being connected to u, is connected to its r closest neighbors to the left and to the right. We prove that if vertices are initially active with probability p > 1/4 then, for large values of r, percolation occurs with probability arbitrarily close to I as n > infinity. Also, if p < 1/4, then the probability of percolation is bounded away from 1. (c) 2014 Elsevier B.V. All rights reserved.



Rapaport, I., Suchan, K., Todinca, I., & Verstraete, J. (2011). On Dissemination Thresholds in Regular and Irregular Graph Classes. Algorithmica, 59(1), 16–34.
Abstract: We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < 1/2. We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.

