Exact GapSVP in all dimensions below a fixed cutoff
ProvedInfoLossLAR.WorstCase.RegevSketch.finite_exact_gaplar-regev-bridgelatticeslearning-with-errorsquantum-computing
For every fixed natural cutoff , there is one uniform quantum polynomial-time family such that, for every positive , it solves exact decision GapSVP in dimension for all nonsingular integer bases and positive rational thresholds. In particular the running time must be polynomial in the full binary instance length, including arbitrarily large matrix entries and thresholds; there is no finite table of instances. A single family handles all dimensions below the fixed cutoff.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch theorem finite_exact_gap (cutoff : ℕ) : ∃ E : Family, IsQPT E ∧ ∀ n : ℕ, 1 ≤ n → n < cutoff → SolvesGapSVP E (famN n) 1 := by sorry end InfoLossLAR.WorstCase.RegevSketch
Source
Daniele Micciancio and Panagiotis Voulgaris, A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations, https://cseweb.ucsd.edu/~daniele/papers/Voronoi.pdf, Introduction and §2 (especially discussion of basis-bit-size dependence). The finite-cutoff circuit-family formulation and the rational-threshold comparison are explicit consequences adapted to the platform encoding, not a verbatim theorem in the paper.