# Halting problems for sandpiles and abelian networks

 Computer Science/Discrete Mathematics Seminar II Topic: Halting problems for sandpiles and abelian networks Speaker: Lionel Levine Affiliation: Cornell University; von Neumann Fellow Date: Tuesday, March 12 Time/Room: 10:30am - 12:30pm/Simonyi Hall 101 Video Link: https://video.ias.edu/csdm/2019/0312-LionelLevine

Will this procedure be finite or infinite? If finite, how long can it last? Bjorner, Lovasz, and Shor asked these questions in 1991 about the following procedure, which goes by the name “abelian sandpile”: Given a configuration of chips on the vertices of a finite directed graph, choose (however you like) a vertex with at least as many chips as out-neighbors, and send one chip from that vertex to each of its out-neighbors. Repeat, until there is no such vertex.

The first part of the talk will be a little tour of “algebraic directed graph theory”, whose main player is the graph Laplacian considered as an *integer* matrix. I’ll tell you about the curious class of coEulerian graphs, for which sandpile halting is easy to decide even though it may require exponentially many steps. A recent theorem of Nguyen and Wood, confirming a conjecture of Koplewitz, shows that coEulerian graphs are not rare: The directed random graph G(n,p) is coEulerian with limiting probability $1/(\zeta(2)\zeta(3)\zeta(4)\cdots )$ where $\zeta$ is the Riemann zeta function. So (in case you were wondering) about 43.6% of all simple directed graphs are coEulerian.

The second part of the talk will focus on computation in abelian networks. These are automata networks, generalizing the abelian sandpile, for which the order of execution does not affect the final output. I’ll state some “local-to-global principles” of the form: If every automaton has property X, then the whole network has X.

The usual Boolean gates are not abelian, but there is a set of simple "abelian logic gates” that suffice to compute any abelian function. These include an infinite family, indexed by prime numbers $p$, computing $x \mapsto \lfloor x/p \rfloor$. For directed acyclic circuits, no finite set of abelian gates suffices. But for circuits allowing a limited type of feedback, a specific set of five gates suffices.