Ruiwen Dong to receive Kleene award at LICS

Congratulations to second-year DPhil student Ruiwen Dong, who will receive the prestigious Kleene award for the best student paper at the Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) to be held in Boston in June.
 
His paper studies algorithmic problems over the special affine group SA(2, Z), which is the group of orientation-preserving affine transformations of the lattice Z^2. The group SA(2, Z) lies between the special linear groups SL(2, Z) and SL(3, Z). While most algorithmic problems admit solutions in SL(2, Z), there have been few known results about SL(3, Z). The author proves decidability and NP-completeness of the ​"Identity Problem" in SA(2, Z). Given a finite set of matrices S, the Identity Problem asks whether there exists a non-empty sequence w in S, such that the product of w is equal to the identity matrix. The paper extends previous results from SL(2, Z), and provides a glimpse into the difficulties of solving algorithmic problems in SL(3, Z).