Improved Algorithms for the Approximate k-List Problem in Euclidean Norm

DOI10.1007/978-3-662-54365-8_2zbMath1404.11144OpenAlexW2584914299MaRDI QIDQ5738781

Elena Kirshanova, Gottfried Herold

Publication date: 13 June 2017

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

Full work available at URL: https://doi.org/10.1007/978-3-662-54365-8_2

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items

Lower bounds on lattice sieving and information set decoding ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Development and analysis of massive parallelization of a lattice basis reduction algorithm ⋮ Does the dual-sieve attack on learning with errors even work? ⋮ A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge ⋮ The randomized slicer for CVPP: sharper, faster, smaller, batchier ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Advanced lattice sieving on GPUs, with tensor cores

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Various proofs of Sylvester's (determinant) identity.
• On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
• Tuple lattice sieving
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• Sieve algorithms for the shortest vector problem are practical
• New directions in nearest neighbor searching with applications to lattice sieving
• On the equidistribution of Hecke points
• A sieve algorithm for the shortest lattice vector problem
• A Simple Derivation of the Wishart Distribution
• On Locally Checkable Properties
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Noise-tolerant learning, the parity problem, and the statistical query model