We show that for any constant a, ZPP/b(n) strictly contains
ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques
are very general and give the same hierarchy for all the common
promise time classes including RTIME, NTIME \cap coNTIME, UTIME,
MATIME, AMTIME and BQTIME.

We show a ... more >>>

We give in this paper a different and simpler proof of the tractability of Mal'tsev contraints.

more >>>

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>