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 >>>

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 ... more >>>

We present a deterministic, log-space algorithm that solves
st-connectivity in undirected graphs. The previous bound on the
space complexity of undirected st-connectivity was
log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and
Zhou. As undirected st-connectivity is
complete for the class of problems solvable by symmetric,
non-deterministic, log-space computations (the class SL), ... more >>>