Best Student Paper Award at ICALP for Ruiwen Dong

Congratulations to Ruiwen Dong, whose paper 'The Identity Problem in Z ≀
Z is decidable' is going to be awarded Best Student Paper at ICALP Track
B in July 2023. ICALP, the EATCS International Colloquium on Automata,
Languages and Programming, is one of the flagship conferences in
Theoretical Computer Science.

His paper studies algorithmic problems over the wreath product of two
copies of the integers (written Z ≀ Z). Roughly speaking, computing in
the group Z ≀ Z can be thought of a Turing machine whose tape cells
contain integers and the machine operates by adding integers to the
cells. The paper proves decidability of the 'Identity Problem' in Z ≀
Z. Given a finite set of elements S in the group, the Identity Problem
asks whether there exists a non-empty sequence w in S, such that the
product of w is equal to the neutral element. This decidability result
contrasts the undecidability of the 'Semigroup Membership Problem',
which asks for the existence of a sequence w whose product is equal to a
given target. The paper tightens the gap between known decidability and
undecidability results, and contributes an important step towards
solving algorithmic problems in larger classes of groups.