Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

Gabriel Istrate. Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lights-out games) to hypergraphs. Theoretical Computer Science , 580, pp. 83-93, 2015.

Abstract: We study a discrete asynchronous dynamical system on hypergraphs that can be regarded as a natural extension of annihilating walks along two directions: first, the interaction topology is a hypergraph; second, the number of particles at a vertex of the hypergraph is an element of a finite ring Z_p of integers modulo an odd number p>= 3. Equivalently, particles move on a hypergraph, with a moving particle at a vertex being replaced by one indistinguishable copy at each neighbor in a given hyperedge; particles at a vertex collectively annihilate when their number reaches p.

The boolean version of this system arose in earlier work motivated by our earlier work on the statistical physics of social balance, generalizes certain lights-out games to finite fields and also has some applications to the complexity of local search procedures.

Our result shows that under a liberal sufficient condition on the nature of the interaction hypergraph there exists a polynomial time algorithm (based on linear algebra over Z_p) for deciding reachability and recurrence of this dynamical system. Interestingly, we provide a counterexample that shows that this connection does not extend to all graphs.

For a preprint version see

Keywords: discrete complex systems, ights-out games, reachability


Posted by Gabriel Istrate


© Ad Astra 2001-2013