Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix

DOI10.1016/0020-0190(92)90134-HzbMATH Open0758.90060OpenAlexW2006958860MaRDI QIDQ1198041FDOQ1198041

Authors: Boleslaw Szymanski, Balaram Sinharoy 

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90134-h

Recommendations

• Approximating CVP to within almost-polynomial factors is NP-hard
• The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm
• The hardness of the closest vector problem with preprocessing
• scientific article; zbMATH DE number 1775383
• Sampling methods for shortest vectors, closest vectors and successive minima

zbMATH Keywords

latticeNP-completenesssatisfiabilityclosest vector problemshortest vector problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Reducibility among combinatorial problems
• Minkowski's Convex Body Theorem and Integer Programming
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• The closest vector problem in tensored root lattices of type A and in their duals
• Approximating CVP to within almost-polynomial factors is NP-hard

This page was built for publication: Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix

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