complex system modelers

Abstract: We prove that prediction for the synchronous two-dimensional majority rule is $\mathrm{P}$-complete under logspace many-one reductions, resolving a problem open for almost three decades. In 1997, Moore established $\mathrm{P}$-completeness in dimension three and higher and conjectured that the two-dimensional case admits an efficient parallel algorithm. We consider an $n\times n$ torus on which each cell follows the majority of its four nearest neighbors and retains its current state in a tie. Given an explicitly specified initial configuration and a time $T$, prediction asks whether a designated cell is in state $+1$ at time $T$. The central challenge is to make independent information streams cross in the plane under a homogeneous, monotone, diffusive local rule. We overcome this obstacle through a temporal encoding of Boolean values: both values generate activity, but are distinguished by signal arrival times. This encoding yields a crossover that preserves both values and composes with wires, duplication, and AND and OR gates to simulate arbitrary monotone Boolean circuits. Thus a local rule that favors agreement can nevertheless transport, combine, and cross independent information in two dimensions. We also prove $\mathrm{P}$-completeness for deciding whether a designated cell ever reaches $+1$, without a prescribed time horizon. The prediction result extends to every uniform symmetric signed majority rule on the same neighborhood, including the minority rule.

Abstract: Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed $δ\in (0,1)$, there exists $C_δ>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-δ)n$ in $G(n,p)$ with high probability whenever $p\ge C_δ\sqrt{\ln k/n}$. Thus, for $k^2=Θ(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.