2026-08-17T07:42:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6642 2024-03-06T10:38:34Z ddc:004 open_access

Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One Stephens-Davidowitz, Noah Lattices SVP CVP We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any gamma <= 1 + O(log n/n), we obtain an efficient dimension-preserving reduction from gamma^{O(n/log n)}-SVP to gamma-GapSVP and an efficient dimension-preserving reduction from gamma^{O(n)}-CVP to gamma-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when gamma = 1. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction - we reduce gamma^{O(n/log n)}-SVP to gamma-unique SVP, a potentially easier problem than gamma-GapSVP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noah Stephens-Davidowitz 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.19 urn:nbn:de:0030-drops-66421 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.19 eng https://creativecommons.org/licenses/by/3.0/legalcode