The complexity of the bootstraping percolation and other problems

DOI10.1016/j.tcs.2012.08.001zbMath1297.68092OpenAlexW2011486153MaRDI QIDQ393154

Pedro Montealegre-Barba, Ioan Todinca, Eric Goles Chacc

Publication date: 16 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.08.001

zbMATH Keywords

computational complexityparallel algorithmsbootstrapping percolationmajority functionsP-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (19)

Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models ⋮ Computational Complexity of Biased Diffusion-Limited Aggregation ⋮ A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ Dynamics of neural networks over undirected graphs ⋮ Cold dynamics in cellular automata: a tutorial ⋮ Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata ⋮ On the complexity of the stability problem of binary freezing totalistic cellular automata ⋮ The complexity of the asynchronous prediction of the majority automata ⋮ Computational complexity of threshold automata networks under different updating schemes ⋮ Majority rule cellular automata ⋮ The complexity of the majority rule on planar graphs ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ Eric Goles ⋮ On the complexity of asynchronous freezing cellular automata ⋮ Sandpile toppling on Penrose tilings: identity and isotropic dynamics ⋮ Computing the probability of getting infected: on the counting complexity of bootstrap percolation ⋮ Amoebae for clustering: a bio-inspired cellular automata method for data classification ⋮ On the impact of treewidth in the computational complexity of freezing dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On dissemination thresholds in regular and irregular graph classes
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• Small Alliances in Graphs
• Random disease on the square grid
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits

This page was built for publication: The complexity of the bootstraping percolation and other problems