Noisy Chinese remaindering in the Lee norm

Igor E. Shparlinski; Ron Steinfield

doi:10.1016/j.jco.2003.08.020

Noisy Chinese remaindering in the Lee norm

Igor E. Shparlinski^*, Ron Steinfield

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

18 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	423-437
Number of pages	15
Journal	Journal of Complexity
Volume	20
Issue number	2-3
DOIs	https://doi.org/10.1016/j.jco.2003.08.020
Publication status	Published - Apr 2004

Keywords

Chinese remaindering
Closets vector problem
Lattices

Access to Document

10.1016/j.jco.2003.08.020

Cite this

@article{44d394ca3922427298aeb69d753b53ba,

title = "Noisy Chinese remaindering in the Lee norm",

abstract = "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.",

keywords = "Chinese remaindering, Closets vector problem, Lattices",

author = "Shparlinski, {Igor E.} and Ron Steinfield",

year = "2004",

month = apr,

doi = "10.1016/j.jco.2003.08.020",

language = "English",

volume = "20",

pages = "423--437",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "ACADEMIC PRESS INC ELSEVIER SCIENCE",

number = "2-3",

}

TY - JOUR

T1 - Noisy Chinese remaindering in the Lee norm

AU - Shparlinski, Igor E.

AU - Steinfield, Ron

PY - 2004/4

Y1 - 2004/4

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

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

KW - Chinese remaindering

KW - Closets vector problem

KW - Lattices

UR - http://www.scopus.com/inward/record.url?scp=1942443590&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2003.08.020

DO - 10.1016/j.jco.2003.08.020

M3 - Article

AN - SCOPUS:1942443590

SN - 0885-064X

VL - 20

SP - 423

EP - 437

JO - Journal of Complexity

JF - Journal of Complexity

IS - 2-3

ER -

Noisy Chinese remaindering in the Lee norm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this