Noisy Chinese remaindering in the Lee norm

摘要

We use lattice reduction to obtain a polynomial time algorithm for recovering an integer (up to a small interval) from its residues modulo sufficiently many primes, when the residues are corrupted by a small additive noise bounded in the Lee norm. Our results are similar to those obtained for Hamming norm, but based on rather different arguments.