
Becker, F., Montealegre, P., Rapaport, I., & Todinca, I. (2021). The role of randomness in the broadcast congested clique model. Inf. Comput., 281, 104669.
Abstract: We study the role of randomness in the broadcast congested clique model. This is a messagepassing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node.
This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results:
If more than one round is allowed, public randomness is as powerful as private randomness.
Oneround publiccoin algorithms can be exponentially more powerful than deterministic algorithms running in several rounds.
Oneround publiccoin algorithms can be exponentially more powerful than oneround privatecoin algorithms.
Oneround privatecoin algorithms can be exponentially more powerful than oneround deterministic algorithms.



Goles, E., & Montealegre, P. (2020). The complexity of the asynchronous prediction of the majority automata. Inf. Comput., 274(SI).
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.



Goles, E., Maldonado, D., & Montealegre, P. (2021). On the complexity of asynchronous freezing cellular automata. Inf. Comput., 281, 104764.
Abstract: In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a lower to a higher state. A cellular automaton is asynchronous if at each timestep only one cell is updated. We define the problem ASYNCUNSTABILITY, which consists in deciding there exists a sequential updating scheme that changes the state of a given cell.
We begin showing that ASYNCUNSTABILITY is in NL for any onedimensional FCA. Then we focus on the family of lifelike freezing CA (LFCA). We study the complexity of ASYNCUNSTABILITY for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NPComplete. (C) 2021 Elsevier Inc. All rights reserved.



Goles, E., Maldonado, D., Montealegre, P., & Ollinger, N. (2020). On the complexity of the stability problem of binary freezing totalistic cellular automata. Inf. Comput., 274, 21 pp.
Abstract: In this paper we study the family of twostate Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: For Algebraic and Topological Rules the STABILITY problem is in NC. For Turing Universal rules the STABILITY problem is PComplete. (C) 2020 Elsevier Inc. All rights reserved.



Ruivo, E. L. P., de Oliveira, P. P. B., MontalvaMedel, M., & Perrot, K. (2020). Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations. Inf. Comput., 274(SI), 104538.
Abstract: Cellular automata are discrete dynamical systems with locally defined behaviour, well known as simple models of complex systems. Classically, their dynamics derive from synchronously iterated rules over finite or infinite configurations; however, since for many natural systems to be modelled, asynchrony seems more plausible, asynchronous iteration of the rules has gained a considerable attention in recent years. One question in this context is how changing the update schedule of rule applications affects the global behaviour of the system. In particular, previous works addressed the notion of maximum sensitivity to changes in the update schemes for finite lattices. Here, we extend the notion to infinite lattices, and classify elementary cellular automata space according to such a property.

