Concept
Why initial parity checks must rule out small violation sets
The support of a binary vector is the set of its one entries; its weight is the number of those entries. The kernel of a binary check matrix A is the set of z with Az=0 modulo two, a binary linear code. If every nonzero kernel vector has weight at least m/P, then any nonsatisfying assignment passing A violates at least m/P clauses. This makes short random clause lists useful: they have a substantial chance of hitting its support. Without this initial guarantee, one violated clause among m could be missed by nearly all short lists. The zero vector must remain allowed, because it represents satisfaction.
0
1
Updated 2026-11-07
Tags
Math