Efficient Algorithms for Stochastic Sandpile Models

Description

The sandpile model was originally introduced by Bak, Tang and Wiesenfeld in the 1980's as an example of a model exhibiting the phenomenon known as self-organised criticality. Since then, it has become a rich research area in various fields, including Mathematics, Computer Science, and Statistical Physics. In this talk, we study a stochastic variant of the sandpile model, known as SSM, where the dynamics of the model are random. We exhibit an efficient burning algorithm for the SSM, which checks in polynomial time whether a given configuration will recur infinitely often in the long-time running of the model. We further improve this algorithm on complete and complete bipartite graphs, obtaining linear algorithms in these specific cases.

Period	12 Oct 2024
Event title	The 8th International Conference on Algorithms, Computing and Systems
Event type	Conference
Conference number	8
Location	Hong KongShow on map
Degree of Recognition	International