CryptoRecords.info
SVP

Shortest Vector Problem

Find a shortest nonzero lattice vector.

Classical · ℓ∞ norm

Exact SVP on arbitrary rational full-rank lattices; ℓ∞ norm

2 results · 2 papers
ClassicalProvableWorst case2c n + o(n)
Results
Compare historyJSONCSV
#PUBLICATION / AUTHORSDATETIME BOUNDSPACE BOUNDEVIDENCE
1Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p normPriyanka MukhopadhyayAlgorithms 2021SourceBibTeX / detailsclassical provable arbitrary lattices ℓ∞19 Dec 202122.443 n + o(n)22.443 n + o(n)PublishedSource checked
2Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity normDivesh Aggarwal · Priyanka MukhopadhyayISAAC 2018SourceBibTeX / detailsclassical provable arbitrary lattices ℓ∞15 May 201822.82 n + o(n)22.82 n + o(n)PublishedSource checked
1–2 of 2 entriesIncludes relevant non-record results. Dates refer to the specific bound.
Comparison definition & assumptions
Regime
Exact SVP on arbitrary rational full-rank lattices; ℓ∞ norm
Computation
Classical
Rigor
Provable
Instances
Worst case
Cost scale
2^{c n + o(n)}
Parameter
n
Description
Proven bounds for exact shortest vectors in ℓ∞ norm.
Comparison rules
Compare exact SVP in the specified norm regime. The norm is part of the problem, not a change of units. Polynomial input-size factors are suppressed; record space and success separately. Source-checked means the stated source claim was checked, not that the proof was independently verified.
Tags
arbitrary lattices, exact SVP, ℓ∞ norm