CryptoRecords.info
CVP

Closest Vector Problem

Find the lattice point closest to a target.

CVP with preprocessing · query cost

Separate lattice-dependent preprocessing from per-target query time

2 results · 2 papers
ClassicalProvableArbitrary targets2c n + o(n)
Results
Compare historyJSONCSV
#PUBLICATION / AUTHORSDATETIME BOUNDSPACE BOUNDEVIDENCE
1Short Paths on the Voronoi Graph and the Closest Vector Problem with PreprocessingDaniel Dadush · Nicolas BonifasSODA 2015SourceBibTeX / detailspreprocessing exact Las Vegas18 Dec 2014Õ(2n) expected query timeÕ(2n) stored advice and spacePublishedSource checked
2A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell ComputationsDaniele Micciancio · Panagiotis VoulgarisSIAM Journal on Computing 2013SourceBibTeX / detailspreprocessing exact2011Õ(22n) query timeÕ(2n) stored advicePublishedSource checked
1–2 of 2 entriesIncludes relevant non-record results. Dates refer to the specific bound.
Comparison definition & assumptions
Regime
Separate lattice-dependent preprocessing from per-target query time
Computation
Classical
Rigor
Provable
Instances
Arbitrary targets
Cost scale
2^{c n + o(n)}
Parameter
n
Description
Query bounds require the preprocessing time and storage to be stated separately.
Comparison rules
Record the exact parameter regime, cost unit, distribution and access assumptions. A source and BibTeX are required for new submissions. This template makes no claim to a universal exponent.
Tags
CVPP, preprocessing, query complexity, arbitrary lattices