Sublinear-Time Probabilistic Cellular Automata

We propose and investigate a probabilistic model of sublinear-time one-dimensional cellular automata. In particular, we modify the model of ACA (which are cellular automata that accept if and only if all cells simultaneously accept) so that every cell changes its state not only dependent on the states it sees in its neighborhood but also on an unbiased coin toss of its own. The resulting model is dubbed \emph{probabilistic ACA} (PACA), accordingly. We consider both one- and two-sided error versions of the model (in the same spirit as the classical Turing machine classes $\mathsf{RP}$ and $\mathsf{BPP}$) and establish a separation between the classes of languages they can recognize all the way up to $o(\sqrt{n})$ time. We also prove that the derandomization of $T(n)$-time PACA (to polynomial-time deterministic cellular automata) for various regimes of $T(n) = \omega(\log n)$ implies non-trivial derandomization results for the class $\mathsf{RP}$ (e.g., $\mathsf{P} = \mathsf{RP}$). Last but not least, as our main contribution we give a full characterization of the constant-time PACA classes: For one-sided error, the class is equal to that of the deterministic model; that is, we prove that constant-time one-sided error PACA can be fully derandomized with only a constant multiplicative overhead in time complexity. As for two-sided error, we characterize the respective class in terms of a linear threshold condition and prove that it lies in-between the class of strictly locally testable languages ($\mathsf{SLT}$) and that of locally threshold testable languages ($\mathsf{LTT}$) while being incomparable to the locally testable languages ($\mathsf{LT}$).