scientific article

DOI10.4086/toc.2012.v008a022zbMath1282.68127OpenAlexW2293438091MaRDI QIDQ2913823

Daniele Micciancio

Publication date: 27 September 2012

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

Full work available at URL: https://doi.org/10.4086/toc.2012.v008a022

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

latticesNP-hardnessshortest vector problemhardness of approximationrandomized reductions

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

Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ List-decoding Barnes-Wall lattices ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ Improving convergence and practicality of slide-type reductions ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ Unnamed Item ⋮ Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors ⋮ The remote set problem on lattices

Cites Work

• Sieve algorithms for the shortest vector problem are practical
• Hardness of approximating the shortest vector problem in lattices
• The intractability of computing the minimum distance of a code
• The hardness of the closest vector problem with preprocessing

This page was built for publication: