Concrete VC-controlled incidence construction
DefinitionNearLogSetCover966_Main_Supplement_VCp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
For a vector-sum instance and a separator test , group equal hash values within each input group. A coordinate is the pair , represented equivalently by . Enumerate the assignments of weight at most that reject the zero-sum test, and set
The auxiliary system has points and sets . The construction uses actual neighborhood classes, rather than adding unused hash symbols. All output variables remain indexed, including coinciding sets.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_FiniteVC
import Definitions.Def_NearLogSetCover966_Main_Supplement_CodeReduction
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
/-- Actual neighborhood classes in a test, represented by their group and hash value.
For k≥2 this is in bijection with the source's pairs (i,P_(r,i,a)). -/
def vcClasses {d : ℕ} (I : VectorSum) (ψ : Mat I.D d) : List (Fin I.k × Vec d) :=
((List.ofFn fun i : Fin I.k => List.ofFn fun a : Fin I.n => (i, ψ.mulVec (I.v i a))).flatten).dedup
noncomputable def vcAccept {d : ℕ} (I : VectorSum) (ψ : Mat I.D d) (z : ℕ) : Prop :=
∃ b : Fin I.k → Vec d, ∑ i, b i = 0 ∧ ∀ i,
∃ a : Fin I.n, ψ.mulVec (I.v i a) = b i ∧
z.testBit ((vcClasses I ψ).idxOf (i, b i)) = true
noncomputable def vcClause {d : ℕ} (I : VectorSum) (ψ : Mat I.D d) (z : ℕ) : Finset (Fin (I.k*I.n)) := by
classical
exact Finset.univ.filter fun a =>
let ia := (finProdFinEquiv : Fin I.k × Fin I.n ≃ Fin (I.k*I.n)).symm a
z.testBit ((vcClasses I ψ).idxOf (ia.1, ψ.mulVec (I.v ia.1 ia.2))) = false
noncomputable def vcFormula {d : ℕ} (I : VectorSum) (H : HashFamily I.D d) (h : ℝ) : MMSA2 := by
classical
exact ⟨I.k*I.n, H.maps.flatMap fun ψ =>
((List.range (2^(vcClasses I ψ).length)).filter fun z =>
(weight (fun i : Fin (vcClasses I ψ).length => z.testBit i.val) : ℝ) ≤ h ∧
¬ vcAccept I ψ z).map (vcClause I ψ)⟩
noncomputable def vcInstance {d : ℕ} (I : VectorSum) (H : HashFamily I.D d) (h : ℝ) : SCInstance :=
clauseInstance (vcFormula I H h)
/-- The auxiliary T-system of §5.1, on the actual test/group/neighborhood triples. -/
noncomputable def auxiliaryVC {d : ℕ} (I : VectorSum) (H : HashFamily I.D d) : ℕ :=
incidenceVC (fun a : Fin I.k × Fin I.n => fun e :
(r : Fin H.maps.length) × {p // p ∈ vcClasses I H.maps[r]} =>
e.2.val = (a.1, H.maps[e.1].mulVec (I.v a.1 a.2)))
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), §5.1, printed pp.23–24 (PDF pp.25–26); Lemma 5.3, printed p.25 (PDF p.27)