Lattice problems and norm embeddings

DOI10.1145/1132516.1132581zbMath1301.68151OpenAlexW1966034053MaRDI 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

embeddingnormslatticeshardness of approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Post-quantum cryptography: lattice signatures ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ A polynomial time algorithm for GapCVPP in \(l_1\) norm ⋮ Information set decoding for Lee-metric codes using restricted balls ⋮ Hardness of approximating the closest vector problem with pre-processing ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ Complexity and approximation of finding the longest vector sum ⋮ A Digital Signature Scheme Based on CVP  ∞ ⋮ Complexity and algorithms for finding a subset of vectors with the longest sum ⋮ Sampling methods for shortest vectors, closest vectors and successive minima ⋮ Approximability of the Problem of Finding a Vector Subset with the Longest Sum ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ The remote set problem on lattices

This page was built for publication: Lattice problems and norm embeddings