Lattice problems and norm embeddings

DOI10.1145/1132516.1132581MaRDI QIDQ2931407zbMATH OpenOpenAlexFDO

Authors 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

embeddinghardness of approximationlatticesnorms

Mathematics Subject Classification ID

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

Recommendations

• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• The Hardness of the Closest Vector Problem With Preprocessing Overell_inftyNorm
• Hardness of approximating the shortest vector problem in lattices
• Sampling methods for shortest vectors, closest vectors and successive minima
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!

Cited in

(26)

• Sampling methods for shortest vectors, closest vectors and successive minima
• Complexity and approximation of finding the longest vector sum
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
• The remote set problem on lattices
• Post-quantum cryptography: lattice signatures
• On norms taking integer values on the integer lattice
• The reductions for the approximating covering radius problem
• Hardness of approximating the closest vector problem with pre-processing
• On the lattice distortion problem
• Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one
• Approximability of the problem of finding a vector subset with the longest sum
• An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• Hardness of bounded distance decoding on lattices in lp norms
• Cryptographic functions from worst-case complexity assumptions
• A Digital Signature Scheme Based on CVP  ∞
• A vector lattice version of r˚ adström's embedding theorem
• scientific article; zbMATH DE number 2207653 (Why is no real title available?)
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Information set decoding for Lee-metric codes using restricted balls
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
• \textsf{FuLeeca}: a Lee-based signature scheme
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
• Topological \(k\)-metrics
• A polynomial time algorithm for GapCVPP in \(l_1\) norm
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms

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

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