Polynomial-time dimension cutoff classifier for GapSVP instance encoding
ProvedInfoLossLAR.WorstCase.RegevSketch.gap_dimension_classifierlar-regev-bridgelatticeslearning-with-errorsquantum-computing
For each fixed natural cutoff there exists a total polynomial-time computable function on binary strings such that on every platform GapSVP instance encoding for a square integer matrix in dimension , and every rational threshold, outputs the one-bit string . Its behavior on malformed strings is unrestricted, but its polynomial running time applies to all strings. No nonsingularity or threshold sign assumption is needed for correctly encoded inputs.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem gap_dimension_classifier (cutoff : ℕ) :
∃ f : Str → Str, PolyTimeComputable f ∧
∀ n : ℕ, ∀ B : Matrix (Fin (famN n)) (Fin (famN n)) ℤ,
∀ δ : ℚ, f (encGapInstance B δ) = [decide (n < cutoff)] := by sorry
end InfoLossLAR.WorstCase.RegevSketchSource
Definitions.Def_InfoLossLAR_WorstCase_Encoding and Definitions.Def_InfoLossLAR_WorstCase_LatticeProblems, encoding definitions for binary strings, matrices and GapSVP instances. This is an elementary, explicit encoding lemma.