Vorträge

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.