Chinese remaindering with errors

The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder module k relatively prime integers p(1), ..., p( k), provided m < Pi(i=1)(k) p(i). Thus the residues of m module relatively prime integers p(1) < p(2) < ... < p(n) form a redundant representation of m if m < Pi(i=1)(k), p(i) and k < n, This gives a number-theoretic construc tion of an "error-correcting code" that has been considered often in the pa st (see [41]; also [35, pp, 325-336]), [19], [35]). In this code a "message " (integer) m < Pi(i=1)(k) p(i) is encoded by the list of its residues modu le p(1), ...., p(n), By the Chinese Remainder Theorem, if a codeword is cor rupted in e < (n - k)/2 coordinates, then there exists a unique integer m w hose corresponding codesword differs from the corrupted word in at most e p laces. Furthermore, Mandelbaum [25], [26] shows how m can be recovered effi ciently given the corrupted word provided that the Pi's are very close to o ne another. To deal with arbitrary p(i)'s, we present a variant of his algo rithm that runs in almost Linear time and recovers from e < log p(1)/log p(1) + log p(n) . (n - k) errors. Our main contribution is an efficient decoding algorithm for the ca se in which the error e may be larger than n-k/2. Specifically, given n res idues r(1), ..., r(n) and an agreement parameter t, we find a list of all i ntegers m < Pi(i=1)(k) p(i) such that (m mod p(i)) = r(i) for at least t va lues of i is an element of {1, ..., n}, provided t = Omega(root kn(log p(n)/log p(1))). For n much greater than k (and p(n) less than or equal to p(1)(O(1))), the fraction of error corrected by the algorithm is almost twice that corrected by the precious work, More significantly, the algorithm recovers the messa ge even when the amount of agreement between the "received word" and the "c odeword" is much smaller than the number of errors.