Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

DOI10.4086/toc.2012.v008a023zbMath1253.68152arXiv1806.04087OpenAlexW2399135883MaRDI QIDQ2913824

Ishay Haviv, Oded Regev

Publication date: 27 September 2012

Published in: Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

latticesNP-hardnessshortest vector problemhardness of approximation

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Lattice packing and covering (number-theoretic aspects) (11H31) Combinatorial aspects of packing and covering (05B40)

Related Items (10)

Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Improved hardness results for unique shortest vector problem ⋮ Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ List-decoding Barnes-Wall lattices ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Inverse Optimization with Noisy Data ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ The remote set problem on lattices

Cites Work

• Minkowski's Convex Body Theorem and Integer Programming
• Unnamed Item

This page was built for publication: Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors