Concrete code-assisted clause construction
DefinitionNearLogSetCover966_Main_Supplement_CodeReductionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
Let have indexed sets and elements. Given additive tables and a binary linear separator, form groups: the first carry the padded original sets and vectors ; the final carry empty sets and vectors . For each hash test and low-weight grouped assignment , let be its zero-sum hash tuples. For each with , enumerate every map and write the actual distributed OR clause
Transposing this clause list gives a finite incidence instance with every variable retained as an indexed set. Empty products and empty clauses have their ordinary Boolean meanings. These definitions assert no correctness or resource guarantee.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_Codes
import Definitions.Def_NearLogSetCover966_Main_Supplement_Oracle
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
def groupVector {k s ell : ℕ} (f : Tables k s ell) (i : Fin (k + ell)) (a : Vec s) : Fin ell → Vec s :=
if hi : i.val < k then f ⟨i.val, hi⟩ a
else fun j => if j.val = i.val - k then -a else 0
def flattenWord {ell s : ℕ} (w : Fin ell → Vec s) : Vec (ell * s) :=
fun z => let ij := (finProdFinEquiv : Fin ell × Fin s ≃ Fin (ell*s)).symm z
w ij.1 ij.2
def groupSet {k s ell : ℕ} (I : SCInstance) (i : Fin (k + ell)) (a : Vec s) : Finset (Fin I.n) :=
if i.val < k then I.sets.getD (vectorIndex a) ∅ else ∅
def hashed {k s ell d : ℕ} (f : Tables k s ell) (ψ : Mat (ell*s) d)
(i : Fin (k+ell)) (a : Vec s) : Vec d := ψ.mulVec (flattenWord (groupVector f i a))
def gammaWords (K d z : ℕ) : List (Fin K → Vec d) :=
(allWords K d).filter fun b =>
decide (∑ i : Fin K, b i = 0) &&
(List.ofFn fun i : Fin K => z.testBit (i.val * 2^d + vectorIndex (b i))).all id
/-- The fully distributed clause for one r,z and one uncovered-element witness for each b.
The natural fcode enumerates all maps Γ(z)→U₀ by base-u₀ digits. Empty products are 1. -/
noncomputable def codeClause {k s ell d : ℕ} (I : SCInstance) (f : Tables k s ell)
(ψ : Mat (ell*s) d) (z fcode : ℕ) : Finset (Fin ((k+ell)*2^s)) := by
classical
exact Finset.univ.filter fun a =>
let ia := (finProdFinEquiv : Fin (k+ell) × Fin (2^s) ≃ Fin ((k+ell)*2^s)).symm a
let v := vectorAt s ia.2.val
let hv := hashed f ψ ia.1 v
¬ z.testBit (ia.1.val * 2^d + vectorIndex hv) = true ∨
∃ j : Fin (gammaWords (k+ell) d z).length,
hv = (gammaWords (k+ell) d z)[j] ia.1 ∧
∃ e : Fin I.n, e.val = (fcode / I.n ^ j.val) % I.n ∧ e ∈ groupSet I ia.1 v
noncomputable def codeFormula {k s ell d : ℕ} (I : SCInstance) (f : Tables k s ell)
(H : HashFamily (ell*s) d) (h : ℝ) (c : ℕ) : MMSA2 :=
⟨(k+ell)*2^s, H.maps.flatMap fun ψ =>
((List.range (2 ^ ((k+ell)*2^d))).filter fun z =>
(weight (fun i : Fin ((k+ell)*2^d) => z.testBit i.val) : ℝ) ≤ h ∧ (gammaWords (k+ell) d z).length ≤ c).flatMap fun z =>
(List.range (I.n ^ (gammaWords (k+ell) d z).length)).map (codeClause I f ψ z)⟩
/-- Transpose an actual clause list into incidence, retaining every variable as an indexed set. -/
def clauseInstance (F : MMSA2) : SCInstance :=
⟨F.clauses.length, List.ofFn fun a : Fin F.n =>
Finset.univ.filter fun e : Fin F.clauses.length => a ∈ F.clauses[e]⟩
noncomputable def codeInstance {k s ell d : ℕ} (I : SCInstance) (f : Tables k s ell)
(H : HashFamily (ell*s) d) (h : ℝ) (c : ℕ) : SCInstance :=
clauseInstance (codeFormula I f H h c)
/-- q=2^s is the least power of two at least the number of indexed sets. -/
def LeastPower (s n : ℕ) : Prop := n ≤ 2^s ∧ ∀ t : ℕ, n ≤ 2^t → s ≤ t
noncomputable def codeReductionInput {k s ell : ℕ} (I : SCInstance)
(f : Tables k s ell) (h : ℝ) (c : ℕ) : Str :=
coverInput I k ++ frame (tableEncode f) ++ thresholdCode h ++ unary c
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), §4.2, printed pp.16–19 (PDF pp.18–21), especially Claim 4.5 and Lemma 4.6