[Model] MinimumWeightDecoding

[isPANN]

Motivation

MINIMUM WEIGHT DECODING (MS7) from Garey & Johnson, A1.2. Given a binary matrix H (parity check matrix) and a syndrome vector s, find a binary vector x satisfying Hx = s over GF(2) that minimizes the Hamming weight (number of ones). This is the fundamental nearest-codeword problem in coding theory — it asks for the minimum-weight error pattern consistent with a given syndrome. NP-hard (Berlekamp, McEliece, van Tilborg 1978). Applications in error-correcting codes, cryptography (McEliece cryptosystem), and lattice problems.

Definition

Name: MinimumWeightDecoding
Reference: Garey & Johnson, Computers and Intractability, A1.2 MS7; Berlekamp, McEliece, van Tilborg 1978

Mathematical definition:

INSTANCE: n×m binary matrix H (over GF(2)), binary vector s of length n.
OBJECTIVE: Find a binary vector x of length m satisfying Hx ≡ s (mod 2) that minimizes the Hamming weight |x| = Σ x_j.

Variables

• Count: m (one per column of H)
• Per-variable domain: {0, 1}
• Meaning: Each variable x_j indicates whether column j of H is included in the linear combination. The constraint is that the sum (mod 2) of selected columns equals s. The objective is to minimize the number of selected columns.

Schema (data type)

Type name: MinimumWeightDecoding
Variants: none (unique input structure)

Field	Type	Description
matrix	Vec<Vec<bool>>	n×m binary matrix H (parity check matrix)
target	Vec<bool>	Binary syndrome vector s of length n

Complexity

• Best known exact algorithm: NP-hard (Berlekamp, McEliece, van Tilborg 1978, transformation from 3-Dimensional Matching). The best known algorithms use information set decoding: Becker, Joux, May, and Meurer (EUROCRYPT 2012) achieve O*(2^(0.0494 · num_cols)) for rate-1/2 codes. More recent nearest-neighbor-based approaches improve this further.
• Complexity string: "2^(0.0494 * num_cols)"

Extra Remark

Full book text:

INSTANCE: n×m binary matrix A, binary n-vector ȳ, positive integer K ≤ m.
QUESTION: Is there a binary m-vector x̄ having at most K ones and satisfying Ax̄ = ȳ over GF(2) (equivalently, Ax̄ ≡ ȳ (mod 2))?

Reference: [Berlekamp, McEliece, and van Tilborg, 1978]. Transformation from 3-DIMENSIONAL MATCHING.
Comment: The problem of computing the minimum Hamming distance of a linear code is a special case.

Note: The original G&J formulation is a decision problem with threshold K. We use the equivalent optimization formulation: minimize the Hamming weight of x subject to Hx = s over GF(2).

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^m binary vectors; check GF(2) constraint; return the one with minimum Hamming weight.)
• It can be solved by reducing to integer programming. (Binary variables with modular arithmetic constraints linearized via integer slack variables; minimize Hamming weight.) See companion issue [Rule] MinimumWeightDecoding to ILP #968.
• Other:

Reduction Rule Crossref

• [Rule] MinimumWeightDecoding to ILP #968 — [Rule] MinimumWeightDecoding to ILP (direct ILP formulation)

Example Instance

Input:
Matrix H (3×4 over GF(2)):

1 0 1 1
0 1 1 0
1 1 0 1

Syndrome vector s = (1, 1, 0).

All feasible solutions (Hx ≡ s mod 2):

• x = (0, 0, 1, 0), weight 1: H·x = (1, 1, 0) ✓
• x = (0, 1, 0, 1), weight 2: H·x = (1, 1, 0) ✓
• x = (1, 1, 0, 0), weight 2: H·x = (1, 1, 0) ✓
• x = (1, 0, 1, 1), weight 3: H·x = (1, 1, 0) ✓

The search space has 2^4 = 16 binary vectors, of which 4 satisfy the GF(2) constraint. The feasible solutions have 3 distinct Hamming weights (1, 2, 3).

Optimal solution: x = (0, 0, 1, 0) — selecting only column 3 of H, which equals s.

Expected Outcome

Optimal value: Min(1) — the minimum Hamming weight of a feasible vector is 1. There are 4 feasible solutions with 3 distinct weight values (1, 2, 3), and a unique optimal solution.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting this problem to the existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Complexity string uses naive brute force; book text transcription has dimension inconsistency
Well-written	❌ Fail	Example too simple; missing Expected Outcome section; dimension inconsistency in Full Book Text

Overall: 1 passed, 2 failed, 1 warning

---

Usefulness

The problem DecodingOfLinearCodes does not yet exist in the codebase — confirmed via pred show.

However, the issue does not mention any concrete reduction rule connecting this problem to the existing reduction graph. The Motivation section describes applications (coding theory, cryptography, lattice problems) but does not name a specific source or target problem for a planned reduction. A problem without any planned reduction rule is an orphan node with no value in the reduction graph.

Verdict: Fail. Add at least one planned reduction to/from an existing problem (e.g., from 3-Dimensional Matching, which is the original NP-completeness proof source, or to ILP).

Non-trivial

The problem has genuinely distinct feasibility constraints: a GF(2) linear system equation combined with a Hamming weight upper bound. No existing problem in the codebase captures this combination. The closest existing problems (ILP, ClosestVectorProblem, FeasibleBasisExtension) operate over different domains or have different constraint structures.

Verdict: Pass.

Correctness

References verified:

• Berlekamp, McEliece, van Tilborg (1978): Confirmed real. "On the inherent intractability of certain coding problems," IEEE Transactions on Information Theory, Vol. 24, No. 3, pp. 384-386. The paper proves NP-completeness of the general decoding problem via reduction from 3-Dimensional Matching. The issue correctly states this.
• Becker, Joux, May, Meurer (2012): Confirmed real. "Decoding Random Binary Linear Codes in 2^{n/20}," EUROCRYPT 2012. The O*(2^{0.0494n}) bound for half-distance decoding is correct.

Complexity string issue: The issue proposes "2^num_cols" as the complexity string, which is naive brute-force enumeration. This does not reflect the best known algorithm. The issue itself mentions Becker et al. achieving O*(2^{0.0494n}), yet the complexity string ignores this. Following project conventions, the complexity string should use the best known exact algorithm bound, e.g., "2^(0.0494 * num_cols)".

Recommendation: Even more recent work (Both-May variants, nearest-neighbor-based approaches) achieves approximately 2^{0.0473n} for half-distance decoding. Consider citing the latest bound.

Dimension inconsistency in Full Book Text: The issue's own definition correctly states "binary vector y of length n" (matching Ax being an n-vector when A is n×m). However, the "Full book text" section transcribes y as "binary m-vector ȳ" — if A is n×m and x is m-dimensional, then Ax is n-dimensional, so y must be n-dimensional. This is either a transcription error or uses a transposed convention. Should be corrected for consistency.

Verdict: Warn (references are real and support the claims, but the complexity string and transcription need correction).

Well-written

Section completeness:

Section	Status
Motivation	Present but missing planned reductions
Name	✅ DecodingOfLinearCodes
Reference	✅ Garey & Johnson A1.2 MS7; Berlekamp et al. 1978
Definition	✅ Well-formed
Variables	✅ Clear
Schema	✅ Appropriate types
Complexity	❌ String "2^num_cols" does not reflect best known algorithm
How to solve	⚠️ Only bruteforce checked; note mentions ILP but it is not checked
Example Instance	❌ Too simple (see below)
Expected Outcome	❌ Missing as a clearly labeled section

Example quality issues:

1. Too simple for round-trip testing. The example has K=2, but a weight-1 solution x=(0,0,1,0) exists. This means any correct-or-buggy implementation that finds any feasible solution will pass. For a feasibility problem, the example should have a mix of satisfying and non-satisfying configurations. A better example would have K set such that some weight-K vectors satisfy Ax=y and others do not, and weight-(K-1) vectors do not satisfy Ax=y.
2. The example actually demonstrates K=1 sufficiency, undermining the purpose of the K=2 setup. The K=2 scenario is trivially true once K=1 works.

Dimension inconsistency: The "Full book text" section says "binary m-vector ȳ" but the definition section says "binary vector y of length n." These contradict each other (see Correctness section).

Verdict: Fail.

Recommendations

• Add at least one planned reduction (e.g., 3DimensionalMatching → DecodingOfLinearCodes following Berlekamp et al., or DecodingOfLinearCodes → ILP).
• Update the complexity string to "2^(0.0494 * num_cols)" citing Becker et al. 2012, or use the latest bound.
• Fix the Full Book Text transcription to use consistent dimensions.
• Provide a harder example where the weight bound K is tight — i.e., feasible at weight K but infeasible at weight K-1 — to enable meaningful round-trip testing.
• Add a clearly labeled "Expected Outcome" section stating the answer (YES/NO) and the witnessing solution.

[isPANN]

Converted from decision framing (DecodingOfLinearCodes with bound K) to optimization framing (MinimumWeightDecoding — minimize Hamming weight). Removed Useless and PoorWritten labels. Companion rule issue to follow: ThreeDimensionalMatching → MinimumWeightDecoding (G&J R324).