On the Complexity of the Abelian Sandpile Model: Communication Complexity and Statistical Mechanics
J. Andres Montoya
Departamento de Matemáticas
Universidad Nacional de Colombia
Bogota, Colombia
jamontoyaa@unal.edu.co
Abstract
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.
