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. 230123 Abstract There has been extensive work on the problem of testing equality of compressed strings represented via straightline 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., SchmidtSchauß 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 Pcomplete. 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 nth 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
