SmallBiasFamily
plain-language theorem explainer
SmallBiasFamily defines a structure assigning to each natural number n a list of XOR systems on n variables, serving as the base type for small-bias constructions in SAT complexity. Researchers in Recognition Science derandomization cite it when instantiating polynomial families such as linearSmallBias. The declaration is a bare structure with a single field and no attached proofs.
Claim. A small-bias family consists of a map sending each natural number $n$ to a list of XOR systems, where each XOR system is a list of XOR constraints over $n$ variables.
background
In the SmallBias module, small-bias families provide explicit generators approximating pairwise independence for XOR constraints in SAT instances. XORSystem n is defined as List (XORConstraint n), a collection of parity constraints on n variables. The structure supplies the common type for families that later receive the HasPolySize predicate asserting a polynomial bound on list length via n.succ.
proof idea
The declaration is a structure definition introducing the field directly. No lemmas are applied; it is a one-line structure declaration that defines the interface for small-bias families.
why it matters
SmallBiasFamily serves as the parent type for linearSmallBias and geoSmallBias instantiations and for the HasPolySize class encoding the polynomial-size property. It supplies the explicit interface in the SAT complexity track, supporting deterministic constructions aligned with the Recognition Science forcing chain. The placeholder status leaves open verification of the pairwise-independence approximation.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.