Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
From MaRDI portal
Publication:5240427
DOI10.4230/OASIcs.SOSA.2018.12zbMath1433.68474arXiv1709.01535OpenAlexW2963101940MaRDI QIDQ5240427
Noah Stephens-Davidowitz, Divesh Aggarwal
Publication date: 25 October 2019
Full work available at URL: https://arxiv.org/abs/1709.01535
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)
Related Items
Covering convex bodies and the closest vector problem, Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!, Property-preserving hash functions for Hamming distance from standard assumptions, Approximate CVP_p in Time 2^{0.802 n}, Unnamed Item, On compact representations of Voronoi cells of lattices, Approximate CVP\(_p\) in time \(2^{0.802n}\), A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP, Hardness of bounded distance decoding on lattices in lp norms, Slide reduction, revisited -- filling the gaps in SVP approximation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On Lovász' lattice reduction and the nearest lattice point problem
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- New bounds in some transference theorems in the geometry of numbers
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- Approximating CVP to within almost-polynomial factors is NP-hard
- The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- A Decade of Lattice Cryptography
- Practical, Predictable Lattice Basis Reduction
- A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
- Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
- Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
- Integer Programming with a Fixed Number of Variables
- A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
- Some optimal codes have structure
- Hardness of approximating the shortest vector problem in lattices
- Trapdoors for hard lattices and new cryptographic constructions
- Minkowski's Convex Body Theorem and Integer Programming
- New directions in nearest neighbor searching with applications to lattice sieving
- A sieve algorithm for the shortest lattice vector problem
- An Inequality for Gaussians on Lattices
- Classical hardness of learning with errors
- On lattices, learning with errors, random linear codes, and cryptography
