Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one

DOI10.4230/LIPICS.APPROX-RANDOM.2016.19zbMATH Open1398.68685arXiv1512.04138OpenAlexW2964295570MaRDI QIDQ4636451FDOQ4636451

Authors: Noah Stephens-Davidowitz 

Publication date: 19 April 2018

Abstract: We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $gammaleq1+O(logn/n)$, we obtain an efficient dimension-preserving reduction from $gamm{a}^{O(n/logn)}$-SVP to $gamma$-GapSVP and an efficient dimension-preserving reduction from $gamm{a}^{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 $gamm{a}^{O(n/logn)}$-SVP to $gamma$-unique SVP, a potentially easier problem than $gamma$-GapSVP.

Full work available at URL: https://arxiv.org/abs/1512.04138

Recommendations

• Inapproximability of the shortest vector problem: toward a deterministic reduction
• Hardness of approximating the shortest vector problem in lattices
• Approximating the closest vector problem using an approximate shortest vector oracle
• Lattice problems and norm embeddings
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions

zbMATH Keywords

latticesCVPSVP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Cited In (6)

• Title not available (Why is that?)
• The reductions for the approximating covering radius problem
• Sieving for closest lattice vectors (with preprocessing)
• Improved hardness results for unique shortest vector problem
• Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
• Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice

This page was built for publication: Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636451)