Lecture Announcement
Date: Monday 23/1/23 at 2:00 pm.
Venue: Lecture Hall 6
Testing equality of compressed strings in Randomised NC
Nikhil Balaji
IIT Delhi.
23-01-23

---

Abstract

There has been extensive work on the problem of testing equality of compressed strings represented via straight-line programs. Efficient algorithms for the problem have been known since the work of Hirschfield et al., Plandowski, Melhorn et al. (1994), Je\.{z} (2012). There are also randomized algorithms known (Gasieniec et al., Schmidt-Schauß and Schnitger); however none of these algorithms are known to be parallelizable and it is open whether the question of testing compressed string equality is P-complete.

K\"{o}nig and Lohrey showed that the problem admits a RNC algorithm by reduction to the polynomial identity testing problem. We present a different RNC algorithm for this problem that is arguably simpler. Our algorithm is based on the cyclotomic identity testing (CIT) problem: given a polynomial f(x_1,\ldots,x_k), decide whether f(\zeta_n^{e_1},\ldots,\zeta_n^{e_k}) is zero, where \zeta_n = e^{2\pi i/n} is a primitive complex n-th root of unity and e_1,\ldots,e_k are integers, represented in binary.

Based on a joint work with Sylvain Perifel, Mahsa Shirmohammadi and James Worrell