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

DOI10.1016/0020-0190(92)90134-HzbMath0758.90060OpenAlexW2006958860MaRDI QIDQ1198041

Boleslaw K. 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-completenesssatisfiabilityshortest vector problemclosest 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

• Unnamed Item
• Minkowski's Convex Body Theorem and Integer Programming
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Reducibility among Combinatorial Problems

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