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

DOI10.1016/0020-0190(92)90134-HMaRDI QIDQ1198041zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3516637 (Why is no real title available?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Minkowski's Convex Body Theorem and Integer Programming
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Reducibility among combinatorial problems

Cited in

(3)

• scientific article; zbMATH DE number 6607548 (Why is no real title available?)
• 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)