{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T15:27:05Z","timestamp":1751383625079,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T00:00:00Z","timestamp":1651363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T00:00:00Z","timestamp":1651363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["K119670","KKP-133864"],"award-info":[{"award-number":["K119670","KKP-133864"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["TKP2020-NKA-06"],"award-info":[{"award-number":["TKP2020-NKA-06"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200020-162884","200021-165977"],"award-info":[{"award-number":["200020-162884","200021-165977"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-185030"],"award-info":[{"award-number":["200021-185030"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["Bolyai Scholarship"],"award-info":[{"award-number":["Bolyai Scholarship"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,6]]},"abstract":"Abstract<\/jats:title>We present algorithms for the$$(1+\\epsilon )$$<\/jats:tex-math>(<\/mml:mo>1<\/mml:mn>+<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimensionn<\/jats:italic>has running time of$$2^{O(n)}(1\/\\epsilon )^n$$<\/jats:tex-math>2<\/mml:mn>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow>n<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We improve this substantially in the following two cases. First, for$$\\ell _p$$<\/jats:tex-math>\u2113<\/mml:mi>p<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norms with$$p>2$$<\/jats:tex-math>p<\/mml:mi>><\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(resp.$$p \\in [1,2]$$<\/jats:tex-math>p<\/mml:mi>\u2208<\/mml:mo>[<\/mml:mo>1<\/mml:mn>,<\/mml:mo>2<\/mml:mn>]<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) fixed, we present an algorithm with a running time of$$2^{O(n)}(1+1\/\\epsilon )^{n\/2}$$<\/jats:tex-math>2<\/mml:mn>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup>(<\/mml:mo>1<\/mml:mn>+<\/mml:mo>1<\/mml:mn>\/<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow>n<\/mml:mi>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(resp.$$2^{O(n)} (1+1\/\\epsilon )^{n\/p}$$<\/jats:tex-math>2<\/mml:mn>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup>(<\/mml:mo>1<\/mml:mn>+<\/mml:mo>1<\/mml:mn>\/<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow>n<\/mml:mi>\/<\/mml:mo>p<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>). This result is based on a geometric covering problem, that was introduced in the context of CVP by Eisenbrand et al.: How many convex bodies are needed to cover the ball of the norm such that, if scaled by factor\u00a02 around their centroids, each one is contained in the$$(1+\\epsilon )$$<\/jats:tex-math>(<\/mml:mo>1<\/mml:mn>+<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-scaled homothet of the norm ball? We provide upper bounds for this$$(2,\\epsilon )$$<\/jats:tex-math>(<\/mml:mo>2<\/mml:mn>,<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-covering number<\/jats:italic>by exploiting themodulus of smoothness<\/jats:italic>of the$$\\ell _p$$<\/jats:tex-math>\u2113<\/mml:mi>p<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-balls. Applying a covering scheme, we can boost any 2-approximation algorithm for CVP to a$$(1+\\epsilon )$$<\/jats:tex-math>(<\/mml:mo>1<\/mml:mn>+<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm with the improved run time, either using a straightforward sampling routine or using the deterministic algorithm of Dadush for the construction of an epsilon net. Second, we consider polyhedral and zonotopal norms. For centrally symmetric polytopes (resp. zonotopes) in$${\\mathbb R}^n$$<\/jats:tex-math>R<\/mml:mi><\/mml:mrow>n<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>withO<\/jats:italic>(n<\/jats:italic>) facets (resp. generated byO<\/jats:italic>(n<\/jats:italic>) line segments), we provide a deterministic$$O(\\log _2(2+1\/\\epsilon ))^{O(n)}$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>2<\/mml:mn><\/mml:msub>(<\/mml:mo>2<\/mml:mn>+<\/mml:mo>1<\/mml:mn>\/<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo><\/mml:mrow>)<\/mml:mo><\/mml:mrow>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time algorithm. This generalizes the result of Eisenbrand et al. which applies to the$$\\ell _\\infty $$<\/jats:tex-math>\u2113<\/mml:mi>\u221e<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm. Finally, we establish a connection between themodulus of smoothness<\/jats:italic>andlattice sparsification<\/jats:italic>. As a consequence, using the enumeration and sparsification tools developped by Dadush, Kun, Peikert, and Vempala, we present a simple alternative to the boosting procedure with the same time and space requirement for$$\\ell _p$$<\/jats:tex-math>\u2113<\/mml:mi>p<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>norms. This connection might be of independent interest.<\/jats:p>","DOI":"10.1007\/s00454-022-00392-x","type":"journal-article","created":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T14:13:43Z","timestamp":1651500823000},"page":"1191-1210","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Covering Convex Bodies and the Closest Vector Problem"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4194-0205","authenticated-orcid":false,"given":"M\u00e1rton","family":"Nasz\u00f3di","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"Venzin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,1]]},"reference":[{"key":"392_CR1","unstructured":"Abdelkader, A., Mount, D.M.: Economical Delone sets for approximating convex bodies. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory (Malm\u00f6 2018). Leibniz International Proceedings in Informatics, vol.\u00a0101, # 4. Leibniz-Zent. Inform., Wadern (2018)"},{"key":"392_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Stephens-Davidowitz, N.: Solving the closest vector problem in $$ 2^n$$ time\u2014the discrete Gaussian strikes again! In: 56th Annual Symposium on Foundations of Computer Science (Berkeley 2015), pp. 563\u2013582. IEEE, Los Alamitos (2015)","DOI":"10.1109\/FOCS.2015.41"},{"key":"392_CR3","unstructured":"Aggarwal, D., Mukhopadhyay, P.: Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm (2018). arXiv:1801.02358"},{"key":"392_CR4","unstructured":"Aggarwal, D., Stephens-Davidowitz, N.: Just take the average! An embarrassingly simple $$2^n$$-time algorithm for SVP (and CVP). In: 1st Symposium on Simplicity in Algorithms (New Orleans 2018). OpenAccess Series in Informatics, vol. 61, # 12. Leibniz-Zent. Inform., Wadern (2018)"},{"key":"392_CR5","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: 33rd Annual ACM Symposium on Theory of Computing (Hersonissos 2001), pp. 601\u2013610. ACM, New York (2001)","DOI":"10.1145\/380752.380857"},{"key":"392_CR6","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: 17th Annual Conference on Computational Complexity (Montreal 2002), pp. 53\u201357. IEEE, Los Alamitos (2002)","DOI":"10.1109\/CCC.2002.1004339"},{"key":"392_CR7","unstructured":"Arora, S.: Probabilistic Checking of Proofs and Hardness of Approximation Problems. PhD thesis, University of California at Berkeley (1994)"},{"issue":"4","key":"392_CR8","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1007\/s00454-016-9856-5","volume":"58","author":"S Arya","year":"2017","unstructured":"Arya, S., da Fonseca, G.D., Mount, D.M.: On the combinatorial complexity of approximating polytopes. Discrete Comput. Geom. 58(4), 849\u2013870 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"18","key":"392_CR9","doi-asserted-by":"publisher","first-page":"1648","DOI":"10.1016\/j.tcs.2008.12.045","volume":"410","author":"J Bl\u00f6mer","year":"2009","unstructured":"Bl\u00f6mer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. Theor. Comput. Sci. 410(18), 1648\u20131665 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"392_CR10","doi-asserted-by":"crossref","unstructured":"B\u00f6r\u00f6czky, K. Jr., Wintsche, G.: Covering the sphere by equal spherical balls. In: Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 25, pp. 235\u2013251. Springer, Berlin (2003)","DOI":"10.1007\/978-3-642-55566-4_10"},{"key":"392_CR11","doi-asserted-by":"crossref","unstructured":"Dadush, D.: A $$O(1\/\\epsilon ^2)^n$$-time sieving algorithm for approximate integer programming. In: 10th Latin American Symposium on Theoretical Informatics (Arequipa 2012). Lecture Notes in Computer Science, vol. 7256, pp. 207\u2013218. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-29344-3_18"},{"key":"392_CR12","unstructured":"Dadush, D.: A deterministic polynomial space construction for $$\\epsilon $$-nets under any norm (2013). arXiv:1311.6671"},{"key":"392_CR13","doi-asserted-by":"crossref","unstructured":"Dadush, D., Kun, G.: Lattice sparsification and the approximate closest vector problem. Theory Comput. 12, # 2 (2016)","DOI":"10.4086\/toc.2016.v012a880"},{"key":"392_CR14","doi-asserted-by":"crossref","unstructured":"Dadush, D., Peikert, Ch., Vempala, S.: Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In: 52nd Annual Symposium on Foundations of Computer Science (Palm Springs 2011), pp. 580\u2013589. IEEE, Los Alamitos (2011)","DOI":"10.1109\/FOCS.2011.31"},{"issue":"2","key":"392_CR15","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00493-003-0019-y","volume":"23","author":"I Dinur","year":"2003","unstructured":"Dinur, I., Kindler, G., Raz, R., Safra, S.: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica 23(2), 205\u2013243 (2003)","journal-title":"Combinatorica"},{"issue":"1","key":"392_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. Assoc. Comput. Mach. 38(1), 1\u201317 (1991)","journal-title":"J. Assoc. Comput. Mach."},{"key":"392_CR17","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., H\u00e4hnle, N., Niemeier, M.: Covering cubes and the closest vector problem. In: 27th Symposium on Computational Geometry (Paris 2011), pp. 417\u2013423. ACM, New York (2011)","DOI":"10.1145\/1998196.1998264"},{"key":"392_CR18","unstructured":"van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04. Mathematische Instituut, University of Amsterdam (1981). https:\/\/www.staff.fnwi.uva.nl\/p.vanemdeboas\/vectors\/abstract.html"},{"key":"392_CR19","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol.\u00a02. Springer, Berlin (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"key":"392_CR20","doi-asserted-by":"crossref","unstructured":"Hunkenschr\u00f6der, Ch., Reuland, G., Schymura, M.: On compact representations of Voronoi cells of lattices. In: Integer Programming and Combinatorial Optimization (Ann Arbor 2019). Lecture Notes in Computer Science, vol. 11480, pp. 261\u2013274. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-17953-3_20"},{"issue":"3","key":"392_CR21","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"392_CR22","doi-asserted-by":"crossref","unstructured":"Lenstra, H.W. Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","DOI":"10.1287\/moor.8.4.538"},{"key":"392_CR23","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1307\/mmj\/1028998906","volume":"10","author":"J Lindenstrauss","year":"1963","unstructured":"Lindenstrauss, J.: On the modulus of smoothness and divergent series in Banach spaces. Mich. Math. J. 10, 241\u2013252 (1963)","journal-title":"Mich. Math. J."},{"issue":"2","key":"392_CR24","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0723-0869(01)80025-6","volume":"19","author":"H Martini","year":"2001","unstructured":"Martini, H., Swanepoel, K.J., Wei\u00df, G.: The geometry of Minkowski spaces\u2014a survey. I. Expos. Math. 19(2), 97\u2013142 (2001)","journal-title":"Expos. Math."},{"key":"392_CR25","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: 42rd Annual ACM Symposium on Theory of Computing (Cambridge 2010), pp. 351\u2013358. ACM, New York (2010)","DOI":"10.1145\/1806689.1806739"},{"issue":"2","key":"392_CR26","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1006\/aima.1999.1903","volume":"152","author":"VD Milman","year":"2000","unstructured":"Milman, V.D., Pajor, A.: Entropy and asymptotic geometry of non-symmetric convex bodies. Adv. Math. 152(2), 314\u2013335 (2000)","journal-title":"Adv. Math."},{"key":"392_CR27","doi-asserted-by":"crossref","unstructured":"Mukhopadhyay, P.: Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in $$\\ell _p$$ norm. Algorithms 14(12), # 362 (2021)","DOI":"10.3390\/a14120362"},{"key":"392_CR28","doi-asserted-by":"crossref","unstructured":"Rademacher, L.: Approximating the centroid is hard. In: 23rd Annual Symposium on Computational Geometry (Gyeongju 2007), pp. 302\u2013305. ACM, New York (2007)","DOI":"10.1145\/1247069.1247123"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00392-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00392-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00392-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T15:06:19Z","timestamp":1727103979000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00392-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["392"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00392-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,5,1]]},"assertion":[{"value":"6 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}