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 construction of an "error-correcting code" that has been considered often in the past (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 module p(1), ...., p(n), By the Chinese Remainder Theorem, if a codeword is corrupted in e < (n - k)/2 coordinates, then there exists a unique integer m whose corresponding codesword differs from the corrupted word in at most e places. Furthermore, Mandelbaum [25], [26] shows how m can be recovered efficiently given the corrupted word provided that the Pi's are very close to one another. To deal with arbitrary p(i)'s, we present a variant of his algorithm 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 case in which the error e may be larger than n-k/2. Specifically, given n residues r(1), ..., r(n) and an agreement parameter t, we find a list of all integers m < Pi(i=1)(k) p(i) such that (m mod p(i)) = r(i) for at least t values 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 message even when the amount of agreement between the "received word" and the "codeword" is much smaller than the number of errors.