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

DOI10.4230/LIPICS.APPROX-RANDOM.2016.19MaRDI QIDQ4636451zbMATH OpenOpenAlexFDO

Authors Noah Stephens-Davidowitz

Publication date 19 April 2018

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

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)

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.

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

Cited in

(6)

• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• Sieving for closest lattice vectors (with preprocessing)
• The reductions for the approximating covering radius problem
• 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)