Testing Equality of Compressed Strings in Randomised NC

29^th June 2023, 13:00 Ashton Lecture Theatre
Dr. Nikhil Balaji
Department of Computer Science and Engineering, IIT Delhi

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ö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,…,x_k), decide whether f(ζ_n^{e_1},…, ζ_n^{e_k}) is zero, where ζ_n = e^{2\ π i/n} is a primitive complex n-th root of unity and e_1,…,e_k are integers, represented in binary.

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