Vorträge

21.07.2022 10:00 Uhr Raum 545/O27 Dr. Nikhil Balaji "Testing equality of compressed strings efficiently in parallel randomized time"

Ulm University

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.
(n^3 time), culminating in the breakthrough work of Jez (n^2 time). There are also
randomized algorithms known, for example Gasieniec et al. (n^2 time) and
Schmidt-Schauß and Schnitger (n^2 time); 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 numerical 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(zeta_n^{e_1}, ... , 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, .... , e_k are integers, represented in binary.