The complexity of some lattice problems

DOI10.1007/10722028_1MaRDI QIDQ2739433zbMATH OpenFDO

Authors Jin-Yi Cai

Publication date 9 July 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10722028_1

zbMATH Keywords

complexitycryptographylattice problemsNP-hardnessshortest vector problem

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Review text

This is a survey of recent developments in the study of the complexity of certain lattice problems, mainly focused on the complexity results of intractability. The author discusses some results of M. Ajtai on reduction of worst-case to average-case for some versions of the shortest vector problem (SVP) and describes its impacts in the area of cryptology. For the entire collection see [Zbl 0960.00039].

Recommendations

• Worst-case complexity, average-case complexity and lattice problems
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
• Inapproximability Results for Computational Problems on Lattices
• scientific article; zbMATH DE number 1559544

Cited in

(19)

• Worst-case complexity, average-case complexity and lattice problems
• Difficult configurations -- on the complexity of LTrL
• The variant of remote set problem on lattices
• Enumeration results on linear complexity profiles and lattice profiles
• LCM Lattices and Stanley Depth: A First Computational Approach
• Lattice problems in NP ∩ coNP
• scientific article; zbMATH DE number 3943037 (Why is no real title available?)
• scientific article; zbMATH DE number 4106925 (Why is no real title available?)
• On the trellis complexity of root lattices and their duals
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• scientific article; zbMATH DE number 841094 (Why is no real title available?)
• A Note on Closed Degrees of Difficulty of the Medvedev Lattice
• Lattice equations and their solutions with complexity of polynomial class
• Inapproximability Results for Computational Problems on Lattices
• scientific article; zbMATH DE number 6292594 (Why is no real title available?)
• scientific article; zbMATH DE number 2196508 (Why is no real title available?)
• Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
• Understanding instance hardness for optimisation algorithms: methodologies, open challenges and post-quantum implications

This page was built for publication: The complexity of some lattice problems

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