By grouping several sites together into one, a cellular automaton can be transformed into another with more states and a smaller neighborhood; if the neighborhood has just two sites, we can think of the resulting CA rule as a binary operation. We show that if the blocked rule satisfies an...

We study some simple models of disease transmission on small-world networks, in which either the probability of infection by a disease or the probability of its transmission is varied, or both. The resulting models display epidemic behavior when the infection or transmission probability rises...

We show that if a cellular automaton in two or more dimensions supports growing "ladders" which can turn or block each other, then it can express arbitrary Boolean circuits. Then the problem of predicting the CA for a finite amount of time becomes P-complete, the question of whether a finite...

We study topological defects in the triangular Ising antiferromagnet, a related model on the square lattice equivalent to the six-vertex ice model, and the three-state antiferromagnetic Potts model on the square lattice. We suggest that in each case, defects are attracted or repelled with a...

We consider sets of rectangles and squares recognized by deterministic and non-deterministic two-dimensional finite-state automata. We show that NFAs are strictly more powerful than DFAs, even for pictures over a one-symbol alphabet. In the process, we show that the pitcure languages recognized...

We apply tiling groups and height functions to tilings of regions in the plane by Wang tiles, which are squares with colored boundaries where the colors of shared edges must match. We define a set of tiles as unambiguous if it contains all tiles equivalent to the identity in its tiling group....

We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero probability transitions in single spin-flip dynamics of the Ising model at zero temperature. <p> We...</p>

The technique of approximating the mean path of Markov chains by differential equations has proved to be a useful tool in analyzing the performance of heuristics on random graph instances. However, only a small family of algorithms can currently be analyzed by this method, due to the need to...

We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while...

We study percolation on small-world networks, which has been proposed as a simple model of the propagation of disease. The occupation probabilities of sites and bonds correspond to the susceptibility of individuals to the disease and the transmissibility of the disease respectively. We give an...