Theorem 6.4 — reduction from query-oblivious PCPs to nearest codeword with preprocessing
ProvedLatticePrepro.ObliviousPCP.pcp_reductionLet a query-oblivious PCP with enumerable predicate families (Definition 6.1) be given, with alphabet , random bits, queries and accepting views, and let be a language for which it has perfect completeness and soundness error . Let be a field, let be an injective -linear map such that every nonzero vector of the code has Hamming weight at least , and let be an integer with
Let and be the code and the targets of Construction 6.2, and let . Then:
- Completeness. For every , .
- Soundness. For every , .
- Size. The code has block length .
The code depends only on the PCP, the encoding map and , not on the instance. So the map sends the instances of to targets within distance of the fixed code , and all other instances to targets at distance more than . This is the combinatorial content of the reduction from to -gap nearest codeword with preprocessing over .
Formalization Note. This is Theorem 6.4 without its running-time claims. The final sentence of the theorem, that the construction is a preprocessing reduction when the parameters are polynomial in the instance length, is therefore not formalized. The hypotheses are weaker than in the paper: and are not assumed, is only a lower bound on the relative distance of the code , and need not be finite. Instances form an arbitrary type. The bound from the proof is the separate theorem card_views_le. is CodeFamily.codeDist, and the exponent is a real power, ε ^ (-(1 : ℝ) / q). The Lean names ε, E, g, ρ, q stand for , , , , .
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Conversions_Codes
import Definitions.Def_LatticePrepro_PCP_Verifier
import Definitions.Def_LatticePrepro_PCP_Code
open LatticePrepro
open LatticePrepro.ObliviousPCP
variable {X : Type} (P : ObliviousPCP X) {F : Type} [Field F] [DecidableEq F] {B : ℕ}theorem LatticePrepro.ObliviousPCP.pcp_reduction {Lang : Set X} {ε δ : ℝ} (hc : P.PerfectlyComplete Lang)
(hs : P.SoundnessError Lang ε) (hε : 0 < ε) {E : (P.Views → F) →ₗ[F] (Fin B → F)}
(hE : Function.Injective E)
(hδ : ∀ c ∈ LinearMap.range E, c ≠ 0 → δ * B ≤ hammingNorm c) {g : ℕ}
(hg : (g : ℝ) < δ * ε ^ (-(1 : ℝ) / P.q)) :
(∀ x ∈ Lang, CodeFamily.codeDist (P.target E g x) (P.code E g) ≤ P.radius B) ∧
(∀ x, x ∉ Lang → g * P.radius B < CodeFamily.codeDist (P.target E g x) (P.code E g)) ∧
Fintype.card (P.Coord B ⊕ Fin (g * P.radius B + 1)) =
(Fintype.card P.Alphabet + g) * P.radius B + 1 := by sorry