The complexity of the bootstraping percolation and other problems
DOI10.1016/J.TCS.2012.08.001zbMATH Open1297.68092OpenAlexW2011486153MaRDI QIDQ393154FDOQ393154
Authors: Ioan Todinca, Eric Goles, Pedro Montealegre-Barba 
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
Recommendations
- PSPACE-completeness of majority automata networks
- The complexity of the asynchronous prediction of the majority automata
- Computational complexity of threshold automata networks under different updating schemes
- The complexity of the majority rule on planar graphs
- A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
computational complexityparallel algorithmsbootstrapping percolationmajority functionsP-completeness
Interacting random processes; statistical mechanics type models; percolation theory (60K35) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
- Title not available (Why is that?)
- Title not available (Why is that?)
- An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
- Small Alliances in Graphs
- Title not available (Why is that?)
- Random disease on the square grid
- On dissemination thresholds in regular and irregular graph classes
Cited In (27)
- Cold dynamics in cellular automata: a tutorial
- Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models
- Majority rule cellular automata
- Linear algebra and bootstrap percolation
- Freezing sandpiles and Boolean threshold networks: equivalence and complexity
- The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
- On the complexity of two-dimensional signed majority cellular automata
- Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata
- The complexity of the majority rule on planar graphs
- Intrinsic universality in automata networks. II: Glueing and gadgets
- Computational Complexity of Biased Diffusion-Limited Aggregation
- Title not available (Why is that?)
- Dynamics of neural networks over undirected graphs
- On the complexity of asynchronous freezing cellular automata
- Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
- Computational complexity of threshold automata networks under different updating schemes
- On the complexity of the stability problem of binary freezing totalistic cellular automata
- The complexity of the asynchronous prediction of the majority automata
- A cube dismantling problem related to bootstrap percolation
- Symmetrizable Boolean networks
- On the parameterized complexity of freezing dynamics
- A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
- Eric Goles
- Amoebae for clustering: a bio-inspired cellular automata method for data classification
- Computing the probability of getting infected: on the counting complexity of bootstrap percolation
- Sandpile toppling on Penrose tilings: identity and isotropic dynamics
- On the impact of treewidth in the computational complexity of freezing dynamics
This page was built for publication: The complexity of the bootstraping percolation and other problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393154)
