Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la

Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lights-out games) to hypergraphs

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Gabriel Istrate

Editorial: Theoretical Computer Science , 580, p.83-93, 2015.


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

Cuvinte cheie: discrete complex systems, ights-out games, reachability