Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR04-097 | 2nd November 2004
VĂ­ctor Dalmau

Malt'sev Constraints made Simple

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

more >>>

TR04-096 | 4th November 2004
Eldar Fischer, Frederic Magniez, Michel de Rougemont

Property and Equivalence Testing on Strings

Revisions: 1

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


TR04-095 | 3rd November 2004
Daniele Micciancio

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

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



previous PreviousNext next


ISSN 1433-8092 | Imprint