Approximate CVP\(_p\) in time \(2^{0.802 n}\). (English) Zbl 07651182
Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 43, 15 p. (2020).
Summary: We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any \(\ell_p\)-norm can be computed in time \(2^{(0.802+\varepsilon)n}\). This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. \(\ell_2\). To obtain our result, we combine the latter algorithm w.r.t. \(\ell_2\), with geometric insights related to coverings.
For the entire collection see [Zbl 1445.68017].
For the entire collection see [Zbl 1445.68017].
MSC:
| 68Wxx | Algorithms in computer science |
Keywords:
shortest and closest vector problem; approximation algorithm; sieving; covering convex bodiesReferences:
| [1] | D. Aggarwal, D. Dadush, and N. Stephens-Davidowitz. Solving the closest vector problem in 2 n time -the discrete gaussian strikes again! In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 563-582, October 2015. doi:10.1109/FOCS.2015.41. · doi:10.1109/FOCS.2015.41 |
| [2] | Divesh Aggarwal, Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. Fine-grained hardness of cvp (p) -everything that we can prove (and nothing else). arXiv preprint, 2019. arXiv:1911.02440. |
| [3] | Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2n time using discrete gaussian sampling. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 733-742, 2015. · Zbl 1321.68426 |
| [4] | Divesh Aggarwal and Priyanka Mukhopadhyay. Faster algorithms for SVP and CVP in the infinity norm. CoRR, abs/1801.02358, 2018. arXiv:1801.02358. |
| [5] | Divesh Aggarwal and Noah Stephens-Davidowitz. (gap/s)eth hardness of svp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 228-238, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/ 3188745.3188840. · Zbl 1427.68101 · doi:10.1145/3188745.3188840 |
| [6] | Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average! An embarrassingly simple 2ˆn-time algorithm for SVP (and CVP). In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA, pages 12:1-12:19, 2018. doi: 10.4230/OASIcs.SOSA.2018.12. · Zbl 1433.68474 · doi:10.4230/OASIcs.SOSA.2018.12 |
| [7] | Miklós Ajtai. The shortest vector problem in l2 is np-hard for randomized reductions (extended abstract). In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, page 10-19, New York, NY, USA, 1998. Association for Computing Machinery. doi:10.1145/276698.276705. · Zbl 1027.68609 · doi:10.1145/276698.276705 |
| [8] | Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 601-610, 2001. doi:10.1145/380752.380857. · Zbl 1323.68561 · doi:10.1145/380752.380857 |
| [9] | Miklós Ajtai, Ravi Kumar, and D. Sivakumar. Sampling short lattice vectors and the closest lattice vector problem. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pages 53-57, 2002. doi:10.1109/CCC.2002.1004339. · doi:10.1109/CCC.2002.1004339 |
| [10] | Sanjeev Arora. Probabilistic Checking of Proofs and Hardness of Approximation Problems. PhD thesis, University of California at Berkeley, Berkeley, CA, USA, 1995. UMI Order No. GAX95-30468. |
| [11] | Shiri Artstein-Avidan and Boaz A Slomka. On weighted covering numbers and the levi-hadwiger conjecture. Israel Journal of Mathematics, 209(1):125-155, 2015. · Zbl 1339.52014 |
| [12] | H. Bennett, A. Golovnev, and N. Stephens-Davidowitz. On the quantitative hardness of cvp. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 13-24, October 2017. doi:10.1109/FOCS.2017.11. · doi:10.1109/FOCS.2017.11 |
| [13] | Ulrich Betke and Martin Henk. Intrinsic volumes and lattice points of crosspolytopes. Monat-shefte für Mathematik, 115(1):27-33, 1993. doi:10.1007/BF01311208. · Zbl 0779.52013 · doi:10.1007/BF01311208 |
| [14] | Johannes Blömer and Stefanie Naewe. Sampling methods for shortest vectors, closest vectors and successive minima. Theor. Comput. Sci., 410(18):1648-1665, 2009. doi:10.1016/j.tcs. 2008.12.045. · Zbl 1220.68057 · doi:10.1016/j.tcs.2008.12.045 |
| [15] | V. Chvatal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3):233-235, August 1979. doi:10.1287/moor.4.3.233. · Zbl 0443.90066 · doi:10.1287/moor.4.3.233 |
| [16] | Daniel Dadush and Gábor Kun. Lattice sparsification and the approximate closest vector problem. Theory of Computing, 12(1):1-34, 2016. doi:10.4086/toc.2016.v012a002. · Zbl 1362.68291 · doi:10.4086/toc.2016.v012a002 |
| [17] | Daniel Dadush, Chris Peikert, and Santosh S. Vempala. Enumerative lattice algorithms in any norm via m-ellipsoid coverings. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 580-589. IEEE Computer Society, 2011. doi:10.1109/FOCS.2011.31. · Zbl 1292.68091 · doi:10.1109/FOCS.2011.31 |
| [18] | 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. doi:10.1007/ s00493-003-0019-y. · Zbl 1049.68072 · doi:10.1007/s00493-003-0019-y |
| [19] | Martin E. Dyer, Alan M. Frieze, and Ravi Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1-17, 1991. doi:10.1145/102782. 102783. · Zbl 0799.68107 · doi:10.1145/102782.102783 |
| [20] | Friedrich Eisenbrand, Nicolai Hähnle, and Martin Niemeier. Covering cubes and the closest vector problem. In Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pages 417-423, 2011. doi:10.1145/1998196.1998264. · Zbl 1283.68358 · doi:10.1145/1998196.1998264 |
| [21] | O. Goldreich, D. Micciancio, S. Safra, and Jean-Pierre Seifert. Approximating shortest lattice vectors is not harder than approximating closet lattice vectors. Inf. Process. Lett., 71(2):55-61, July 1999. doi:10.1016/S0020-0190(99)00083-6. · Zbl 0999.68085 · doi:10.1016/S0020-0190(99)00083-6 |
| [22] | Peter Gruber. Convex and Discrete Geometry. Encyclopedia of Mathematics and its Applica-tions. Springer, 2007. · Zbl 1139.52001 |
| [23] | Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 469-477, 2007. · Zbl 1232.68066 |
| [24] | Martin Henk, Jürgen Richter-Gebert, and Günter M Ziegler. Basic properties of convex polytopes. In Handbook of discrete and computational geometry, pages 243-270. CRC Press, 1997. · Zbl 0911.52007 |
| [25] | Varun Jog and Venkat Anantharam. A geometric analysis of the awgn channel with a (σ, ρ)-power constraint. IEEE Transactions on Information Theory, April 2015. doi:10.1109/TIT. 2016.2580545. · Zbl 1359.94260 · doi:10.1109/TIT.2016.2580545 |
| [26] | Grigorii Anatol’evich Kabatiansky and Vladimir Iosifovich Levenshtein. On bounds for packings on a sphere and in space. Problemy Peredachi Informatsii, 14(1):3-25, 1978. · Zbl 0407.52005 |
| [27] | 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. · Zbl 0639.90069 · doi:10.1287/moor.12.3.415 |
| [28] | Subhash Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789-808, September 2005. doi:10.1145/1089023.1089027. · Zbl 1323.68301 · doi:10.1145/1089023.1089027 |
| [29] | A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, 1982. doi:10.1007/BF01457454. · Zbl 0488.12001 · doi:10.1007/BF01457454 |
| [30] | Hendrik W. Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548, 1983. doi:10.1287/moor.8.4.538. · Zbl 0524.90067 · doi:10.1287/moor.8.4.538 |
| [31] | Mingjie Liu, Xiaoyun Wang, Guangwu Xu, and Xuexin Zheng. Shortest lattice vectors in the presence of gaps. IACR Cryptology ePrint Archive, 2011:139, 2011. |
| [32] | Daniele Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM journal on Computing, 30(6):2008-2035, 2001. · Zbl 0980.68054 |
| [33] | Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 351-358, 2010. doi:10.1145/1806689.1806739. 43:15 · Zbl 1293.68172 · doi:10.1145/1806689.1806739 |
| [34] | Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, page 1468-1480, USA, 2010. Society for Industrial and Applied Mathematics. · Zbl 1288.94076 |
| [35] | Priyanka Mukhopadhyay. Faster provable sieving algorithms for the shortest vector problem and the closest vector problem on lattices in p norm. CoRR, abs/1907.04406, 2019. arXiv: 1907.04406. |
| [36] | Márton Naszódi and Moritz Venzin. Covering convex bodies and the closest vector problem. arXiv preprint, 2019. arXiv:1908.08384. |
| [37] | Márton Naszódi. On some covering problems in geometry. Proceedings of the American Mathematical Society, 144, April 2014. doi:10.1090/proc/12992. · Zbl 1341.52031 · doi:10.1090/proc/12992 |
| [38] | Xavier Pujol and Damien Stehlé. Solving the shortest lattice vector problem in time 2 2.465n. IACR Cryptology ePrint Archive, 2009:605, January 2009. |
| [39] | Oded Regev. Lattices in computer science, lecture 8: 2 O(n) algorithm for svp, 2004. |
| [40] | Rolf Schneider. Convex Bodies: The Brunn-Minkowski Theory. Encyclopedia of Math-ematics and its Applications. Cambridge University Press, 2 edition, 2013. doi:10.1017/ CBO9781139003858. · Zbl 1287.52001 · doi:10.1017/CBO9781139003858 |
| [41] | Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical computer science, 53(2-3):201-224, 1987. · Zbl 0642.10030 |
| [42] | P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Mathematische Instituut, University of Amsterdam, 1981. |
| [43] | Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
