A binary polynomial-time exact GapSVP decider below a fixed cutoff
ProvedInfoLossLAR.WorstCase.RegevSketch.finite_exact_gap_binary_decideralgorithmslar-regev-bridgelattices
Fix a natural number . There exists one deterministic polynomial-time program on bit strings with the following guarantee. For every dimension , every nonsingular , and every positive rational threshold , on input the canonical encoding of its first output bit is true exactly when
where is the shortest nonzero vector length in the lattice generated by the columns of .
The running time is polynomial in the full binary encoding length, including the matrix entries and threshold. This lemma isolates the classical computation needed for the uniform QPT formulation.
Preamble
import Definitions.Def_InfoLossLAR_WorstCase_LatticeProblems import Definitions.Def_QuantumMaxCutFiniteNumericRuntime set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem finite_exact_gap_binary_decider (cutoff : ℕ) :
∃ f : Str → Str, Nonempty (OAI.MetricKMedian.Binary.PolyProgram id id f) ∧
∀ n : ℕ, 1 ≤ n → n < cutoff →
∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 →
∀ δ : ℚ, 0 < δ →
((f (encGapInstance B δ))[0]? = some true ↔ lam1 B ≤ (δ : ℝ)) := by
sorry
end InfoLossLAR.WorstCase.RegevSketchSource
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 (basis bit length). The proof uses Lenstra, Lenstra and Lovász, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982), §1, Proposition (1.26), https://doi.org/10.1007/BF01457454, for the basis-reduction method. The exact decision comparison and concrete program and encoding are adaptations.