The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Closest point search in lattices
Open accessAbstract
In this semitutorial paper, a comprehensive survey of closest point search methods for lattices without a regular structure is presented. The existing search strategies are described in a unified framework, and differences between them are elucidated. An efficient closest point search algorithm, based on the Schnorr-Euchner (1995) variation of the Pohst (1981) method, is implemented. Given an arbitrary point x /spl isin/ /spl Ropf//sup m/ and a generator matrix for a lattice /spl Lambda/, the algorithm computes the point of /spl Lambda/ that is closest to x. The algorithm is shown to be substantially faster than other known methods, by means of a theoretical comparison with the Kannan (1983, 1987) algorithm and an experimental comparison with the Pohst (1981) algorithm and its variants, such as the Viterbo-Boutros (see ibid. vol.45, p.1639-42, 1999) decoder. Modifications of the algorithm are developed to solve a number of related search problems for lattices, such as finding a shortest vector, determining the kissing number, computing the Voronoi (1908)-relevant vectors, and finding a Korkine-Zolotareff (1873) reduced basis.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
Vector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,003
Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
Viterbi, A. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1054010 · Cited by 6,759
An Introduction to Probability Theory and Its Applications.
Bharucha-Reid, A. T., & Feller, W. (1967) · The American Mathematical Monthly · doi:10.2307/2314609 · Cited by 6,066
The Art of Computer Programming
Whitesides, G. E. (1970) · Nuclear Science and Engineering · doi:10.13182/nse70-a19705 · Cited by 6,008
Forney, G. D. (1973) · Proceedings of the IEEE · doi:10.1109/proc.1973.9030 · Cited by 5,647
Factoring polynomials with rational coefficients
Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982) · Mathematische Annalen · doi:10.1007/bf01457454 · Cited by 4,018
A Course in Computational Algebraic Number Theory
Cohen, H. (1993) · Graduate Texts in Mathematics · doi:10.1007/978-3-662-02945-9 · Cited by 2,567
Applied Numerical Linear Algebra
Demmel, J. W. (1997) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971446 · Cited by 2,299
Sphere Packings, Lattices and Groups
Conway, J. H., & Sloane, N. J. A. (1999) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-1-4757-6568-7 · Cited by 2,223
Linear algebra and its applications
(1989) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(89)90164-x · Cited by 2,001
(2018) · De Gruyter eBooks · doi:10.1515/9783110542400 · Cited by 1,876
A universal lattice code decoder for fading channels
Viterbo, E., & Bouros, J. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.771234 · Cited by 1,513
Fincke, U., & Pohst, M. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777278-8 · Cited by 1,458
Lattice basis reduction: Improved practical algorithms and solving subset sum problems
Schnorr, C. P., & Euchner, M. (1994) · Mathematical Programming · doi:10.1007/bf01581144 · Cited by 1,427
Voronoi, G. (1908) · Journal für die reine und angewandte Mathematik (Crelles Journal) · doi:10.1515/crll.1908.133.97 · Cited by 945
On Lovász’ lattice reduction and the nearest lattice point problem
Babai, L. (1986) · Combinatorica · doi:10.1007/bf02579403 · Cited by 938
Minkowski's Convex Body Theorem and Integer Programming
Kannan, R. (1987) · Mathematics of Operations Research · doi:10.1287/moor.12.3.415 · Cited by 777
A hierarchy of polynomial time lattice basis reduction algorithms
Schnorr, C. P. (1987) · Theoretical Computer Science · doi:10.1016/0304-3975(87)90064-8 · Cited by 648
A public-key cryptosystem with worst-case/average-case equivalence
Ajtai, M., & Dwork, C. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258604 · Cited by 642
Generating Hard Instances of Lattice ProblemsPreprint
Ajtai, M. (1996) · Electronic colloquium on computational complexity · Cited by 606
Improved algorithms for integer programming and related lattice problems
Kannan, R. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808749 · Cited by 441
Pohst, M. (1981) · ACM SIGSAM Bulletin · doi:10.1145/1089242.1089247 · Cited by 352
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1472 · Cited by 344
Good lattice constellations for both Rayleigh fading and Gaussian channels
Boutros, J. J., Viterbo, E., Rastello, C., & Belfiore, J.-C. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.485720 · Cited by 329
Fischer, T. R. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057198 · Cited by 303
Fourier Analysis of Uniform Random Number Generators
Coveyou, R. R., & Macpherson, R. D. (1967) · Journal of the ACM · doi:10.1145/321371.321379 · Cited by 295
Korkine, A., & Zolotareff, G. (1873) · Mathematische Annalen · doi:10.1007/bf01442795 · Cited by 287
The Shortest Vector Problem in L 2 is NP-hard for Randomized Reductions.Preprint
Ajtai, M. (1997) · Electronic colloquium on computational complexity · Cited by 243
Chinese remaindering with errors
Goldreich, O., Ron, D., & Sudan, M. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850672 · Cited by 226
Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction
Schnorr, C.-P., & Hörner, H. H. (1995) · Lecture notes in computer science · doi:10.1007/3-540-49264-x_1 · Cited by 160
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
Goldreich, O., Micciancio, D., Safra, M., & Seifert, J. (1999) · Information Processing Letters · doi:10.1016/s0020-0190(99)00083-6 · Cited by 146
On the Voronoi Regions of Certain Lattices
Conway, J. H., & Sloane, N. J. A. (1984) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0605031 · Cited by 92
Jeong, D., & Gibson, J. D. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.256488 · Cited by 89
How to Calculate Shortest Vectors in a Lattice
Dieter, U. (1975) · Mathematics of Computation · doi:10.1090/s0025-5718-1975-0379386-6 · Cited by 73
Geometric source coding and vector quantization
Fischer, T. R. (1989) · IEEE Transactions on Information Theory · doi:10.1109/18.42184 · Cited by 71
Maximum likelihood decoding of the Leech lattice
Vardy, A., & Be'ery, Y. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.243466 · Cited by 69
Self-citationGibson, J. D., & Sayood, K. (1988) · Advances in electronics and electron physics · doi:10.1016/s0065-2539(08)60560-0 · Cited by 62
Lattice decoding for joint detection in direct-sequence CDMA systems
Brunel, L., & Boutros, J. J. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.809506 · Cited by 60
On the complexity of decoding lattices using the Korkin-Zolotarev reduced basis
Banihashemi, A. H., & Khandani, A. K. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.651011 · Cited by 52
Optimization of lattices for quantization
Agrell, E., & Eriksson, T. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.705561 · Cited by 49
Self-citationComputing the Voronoi cell of a lattice: the diamond-cutting algorithm
Viterbo, E., & Biglieri, E. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.481786 · Cited by 46
Trellis complexity and minimal trellis diagrams of lattices
Banihashemi, A. H., & Blake, I. F. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.705562 · Cited by 23
Trellis complexity versus the coding gain of lattices. I
Tarokh, V., & Blake, I. F. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556675 · Cited by 17
Cited by
Space-Time Block Coding for Wireless Communications
Larsson, E. G., & Stoica, P. (2003) · Cambridge University Press eBooks · doi:10.1017/cbo9780511550065 · Cited by 1,035
Fifty Years of MIMO Detection: The Road to Large-Scale MIMOs
Yang, S., & Hanzo, L. (2015) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2015.2475242 · Cited by 814
Achieving<tex>$ 1over 2log (1+ hboxSNR)$</tex>on the AWGN Channel With Lattice Encoding and Decoding
Erez, U., & Zamir, R. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834787 · Cited by 732
On the complexity of sphere decoding in digital communications
Jalden, J., & Ottersten, B. (2005) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2005.843746 · Cited by 720
Samuel, N., Diskin, T., & Wiesel, A. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2899805 · Cited by 515
Metadata
- Authors
- Agrell, E., Eriksson, T., Vardy, A., & Zeger, K.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2002-08
- Volume
- 48
- Issue
- 8
- Pages
- 2201-2214
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2140940105
- Cited by
- 1,412
- References
- 44
- FWCI
- 145.61
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.