Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One

Noah Stephens-Davidowitz

We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $\gamma \le 1+O(\log n/n)$, we obtain an efficient dimension-p…