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

摘要

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.