Lattice problems and norm embeddings

DOI10.1145/1132516.1132581zbMath1301.68151MaRDI QIDQ2931407

Ricky Rosen, Oded Regev

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132581

zbMATH Keywords

embedding; norms; lattices; hardness of approximation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11H06: Lattices and convex bodies (number-theoretic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Approximability of the Problem of Finding a Vector Subset with the Longest Sum, Cryptographic Functions from Worst-Case Complexity Assumptions, A Digital Signature Scheme Based on CVP  ∞, Complexity and algorithms for finding a subset of vectors with the longest sum, Hardness of approximating the closest vector problem with pre-processing, An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm, A polynomial time algorithm for GapCVPP in \(l_1\) norm, Sampling methods for shortest vectors, closest vectors and successive minima, Complexity and approximation of finding the longest vector sum, The remote set problem on lattices, Post-quantum cryptography: lattice signatures