Complex Systems

On the Complexity of the Abelian Sandpile Model: Communication Complexity and Statistical Mechanics Download PDF

J. Andres Montoya
Departamento de Matemáticas
Universidad Nacional de Colombia
Bogota, Colombia


In this paper, the complexity of recognizing the critical configurations of the two-dimensional Abelian sandpile model is studied, some known facts are reviewed, and a simplified proof of the burning test is presented. Then, the existence of sublinear time algorithms solving the aforementioned problem is studied, with a lower bound for the monotone complexity of the problem established by employing some tools of communication complexity.