Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction
Theory of Computing, Volume 8(22), pp. 487-512, 2012
Bibliography with links to cited articles
[1] Miklós Ajtai: The shortest vector problem in L2 is NP-hard for randomized reductions. In Proc. 30th STOC, pp. 10–19. ACM Press, 1998. ECCC. [doi:10.1145/276698.276705]
[2] Miklós Ajtai, Ravi Kumar, and D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. In Proc. 33rd STOC, pp. 601–610. ACM Press, 2001. [doi:10.1145/380752.380857]
[3] Sanjeev Arora, László Babai, Jacques Stern, and Elizabeth Z. Sweedyk: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. System Sci., 54(2):317–331, 1997. Preliminary version in FOCS’93. [doi:10.1006/jcss.1997.1472]
[4] Per Austrin and Subhash Khot: A simple deterministic reduction for the gap minimum distance of code problem. In Proc. 38th Internat. Colloq. on Automata, Languages and Programming (ICALP’11), pp. 474–485. Springer, 2011. [doi:10.1007/978-3-642-22006-7_40]
[5] Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alex Russell: Efficient probabilistically checkable proofs and applications to approximations. In Proc. 25th STOC, pp. 294–304. ACM Press, 1993. [doi:10.1145/167088.167174]
[6] Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg: On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory, 24(3):384–386, 1978. [doi:10.1109/TIT.1978.1055873]
[7] Jin-Yi Cai and Ajay Nerurkar: Approximating the SVP to within a factor (1+1/dimϵ) is NP-hard under randomized reductions. J. Comput. System Sci., 59(2):221–239, 1999. Preliminary version in CCC’98. [doi:10.1006/jcss.1999.1649]
[8] Qi Cheng and Daqing Wan: A deterministic reduction for the gap minimum distance problem. In Proc. 41st STOC, pp. 33–38. ACM Press, 2009. [doi:10.1145/1536414.1536421]
[9] John H. Conway and Neil J. A. Sloane: Sphere Packings, Lattices and Groups. Springer, 3rd edition, 1998.
[10] Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, 2003. Preliminary version in FOCS’98. [doi:10.1007/s00493-003-0019-y]
[11] Ilya Dumer, Daniele Micciancio, and Madhu Sudan: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inform. Theory, 49(1):22–37, 2003. Preliminary version in FOCS’99. [doi:10.1109/TIT.2002.806118]
[12] Ishay Haviv and Oded Regev: Tensor-based hardness of the Shortest Vector Problem to within almost polynomial factors. Theory of Computing, 8(23):513–531, 2012. Preliminary version in STOC’07. [doi:10.4086/toc.2012.v008a023]
[13] David S. Johnson: A catalog of complexity classes. In Handbook of Theoretical Computer Science, volume A (Algorithms and Complexity), chapter 2, pp. 67–161. Elsevier, 1990.
[14] Subhash Khot: Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789–808, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089027]
[15] Subhash Khot: Hardness of approximating the shortest vector problem in high ℓp norms. J. Comput. System Sci., 72(2):206–219, 2006. Preliminary version in FOCS’03. [doi:10.1016/j.jcss.2005.07.002]
[16] Yoshiyuki Kitaoka: Tensor products of positive definite quadratic forms. Proc. Japan Acad., 52(9):498–500, 1976. [doi:10.3792/pja/1195518215]
[17] Jeffery C. Lagarias and Andrew M. Odlyzko: Solving low-density subset sum problems. J. ACM, 32(1):229–246, 1985. Preliminary version in FOCS’83. [doi:10.1145/2455.2461]
[18] Vadim Lyubashevsky and Daniele Micciancio: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In 29th Ann. Internat. Cryptology Conf. (CRYPTO’09), pp. 577–594. Springer, 2009. [doi:10.1007/978-3-642-03356-8_34]
[19] Daniele Micciancio: The hardness of the closest vector problem with preprocessing. IEEE Trans. Inform. Theory, 47(3):1212–1215, 2001. [doi:10.1109/18.915688]
[20] Daniele Micciancio: The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput., 30(6):2008–2035, 2001. Preliminary version in FOCS’98. [doi:10.1137/S0097539700373039]
[21] Daniele Micciancio and Shafi Goldwasser: Complexity of Lattice Problems: a cryptographic perspective. Volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 2002.
[22] Daniele Micciancio and Panagiotis Voulgaris: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In Proc. 42nd STOC, pp. 351–358. ACM Press, 2010. ECCC. [doi:10.1145/1806689.1806739]
[23] Daniele Micciancio and Panagiotis Voulgaris: Faster exponential time algorithms for the shortest vector problem. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 1468–1480. ACM Press, 2010. ECCC. [ACM:1873720]
[24] Phong Q. Nguyen and Thomas Vidick: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptology, 2(2):181–207, 2008. [doi:10.1515/JMC.2008.009]
[25] Vera S. Pless and William Cary Huffman, editors. Handbook of Coding Theory. North-Holland, 1998.
[26] Xavier Pujol and Damien Stehlé: Solving the shortest lattice vector problem in time 22.465n. Report 2009/605, IACR ePrint archive, 2009. IACR.
[27] Oded Regev and Ricky Rosen: Lattice problems and norm embeddings. In Proc. 38th STOC, pp. 447–456. ACM Press, 2006. [doi:10.1145/1132516.1132581]
[28] Norbert Sauer: On the density of families of sets. J. Combin. Theory Ser. A, 13(1):145–147, 1972. [doi:10.1016/0097-3165(72)90019-2]
[29] Saharon Shelah: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41(1):247–261, 1972. Project Euclid.
[30] Peter van Emde Boas: Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Mathematische Instituut, University of Amsterdam, 1981. Available at author’s home page.
[31] Vladimir N. Vapnik and Alexey Ya. Chervonenkis: On the uniform covergence of relative frequencies of events to their probabilities. Theory of Probability and Appl., XVI(2):264–280, 1971. Translation from the Russian.
[32] Alexander Vardy: The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory, 43(6):1757–1766, 1997. [doi:10.1109/18.641542]
[33] Xiaoyun Wang, Mingjie Liu, Chengliang Tian, and Jingguo Bi: Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. In Proc. 6th ACM Symp. on Information, Computer and Communications Security (ASIACCS’11), pp. 1–9. ACM Press, 2011. [doi:10.1145/1966913.1966915]