TY - JOUR AU - Miltersen, Peter Bro PY - 1999/01/03 Y2 - 2024/03/19 TI - Two Notes on the Computational Complexity of One-Dimensional Sandpiles JF - BRICS Report Series JA - BRICS VL - 6 IS - 3 SE - Articles DO - 10.7146/brics.v6i3.20060 UR - https://tidsskrift.dk/brics/article/view/20060 SP - AB - We prove that the one-dimensional sandpile prediction problem is<br />in AC1. The previously best known upper bound on the ACi-scale<br />was AC2. We also prove that it is not in AC1−epsilon for any constant<br /> epsilon > 0. ER -