Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

by Ishay Haviv and Oded Regev

Theory of Computing, Volume 8(23), pp. 513-531, 2012

Bibliography with links to cited articles

[1]   Dorit Aharonov and Oded Regev: Lattice problems in NP coNP. J. ACM, 52(5):749–765, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089025]

[2]   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]

[3]   Miklós Ajtai: Generating hard instances of lattice problems. In Complexity of Computations and Proofs, volume 13 of Quad. Mat., pp. 1–32. Dept. Math., Seconda Univ. Napoli, Caserta, 2004. Preliminary version in STOC’96.

[4]   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]

[5]   Noga Alon and Joel H. Spencer: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, second edition, 2000. [doi:10.1002/0471722154]

[6]   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]

[7]   László Babai: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1–13, 1986. Preliminary version in STACS’85. [doi:10.1007/BF02579403]

[8]   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]

[9]   Rajendra Bhatia: Matrix Analysis. Springer, 1997.

[10]   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 at CCC’98. [doi:10.1006/jcss.1999.1649]

[11]   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]

[12]   Henri Cohen: A Course in Computational Algebraic Number Theory. Volume 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993.

[13]   Ehud de Shalit and Ori Parzanchevski: On tensor products of semistable lattices, 2006. Preprint available at author’s home page.

[14]   Irit Dinur: Approximating SVP to within almost-polynomial factors is NP-hard. Theoret. Comput. Sci., 285(1):55–71, 2002. Preliminary version in CIAC’00. [doi:10.1016/S0304-3975(01)00290-0]

[15]   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]

[16]   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]

[17]   Oded Goldreich and Shafi Goldwasser: On the limits of nonapproximability of lattice problems. J. Comput. System Sci., 60(3):540–563, 2000. Preliminary version in STOC’98. [doi:10.1006/jcss.1999.1686]

[18]   Ravi Kannan: Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415–440, 1987. [doi:10.1287/moor.12.3.415]

[19]   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]

[20]   Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász: Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. [doi:10.1007/BF01457454]

[21]   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]

[22]   Daniele Micciancio: Efficient reductions among lattice problems. In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’08), pp. 84–93. ACM Press, 2008. [ACM:1347082.1347092]

[23]   Daniele Micciancio: Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing, 8(22):487–512, 2012. ECCC. [doi:10.4086/toc.2012.v008a022]

[24]   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, Boston, MA, 2002.

[25]   Daniele Micciancio and Oded Regev: Lattice-based cryptography. In D. J. Bernstein and J. Buchmann, editors, Post-Quantum Cryptography, pp. 147–191. Springer, 2009. [doi:10.1007/978-3-540-88702-7_5]

[26]   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. [ACM:1806689.1806738]

[27]   John W. Milnor and Dale Husemöller: Symmetric Bilinear Forms. Springer, Berlin, 1973.

[28]   Hermann Minkowski: Geometrie der Zahlen. I. B. G. Teubner, Leipzig, 1896.

[29]   Christos H. Papadimitriou: Computational Complexity. Addison Wesley Longman, 1994.

[30]   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]

[31]   Claus-Peter Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci., 53(2-3):201–224, 1987. [doi:10.1016/0304-3975(87)90064-8]

[32]   Peter van Emde Boas: Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Math Inst., University of Amsterdam, Amsterdam, 1981. Available at author’s home page.