On the predictability of the abelian sandpile model.

We study two questions related to the abelian sandpile model, those questions are: can we predict the dynamics of sandpiles avalanches? Can we efficiently stop an evolving avalanche? We study the problem of deciding wether all the nodes of a sandpile grid will be toppled by an evolving avalanche. We identify an important subproblem of this prediction problem, namely: the problem of recognizing the recurrent configurations of the sandpile dynamics. This latter problem can be solved in linear time by simulating the appropriate sandpile avalanches. We ask: do there exist sequential algorithms that solve this recognition problem in sublinear time? We prove that there do not exist sublinear time sequential algorithms that solve this problem in a probabilistic approximately correct way. This means that those avalanches cannot be predicted by a sequential algorithm. We also study the problem of fighting against avalanches. This latter problem resembles the classical firefighter problem. We prove that fighting against two-dimensional avalanches is harder than fighting against fires on forests of low depth. [ABSTRACT FROM AUTHOR]