Sparse parity under the spatial cost model

Literature anchors, operation-count sanity checks, and the effect of distance-priced memory on the implemented decoders — companion analysis to the benchmark report. August 26, 2026.

Headline findings

1. The implemented methods sit where theory says they should. Pooled over 12,288 fresh instances at n=32, one Prange/ISD restart recovers the secret 4.22% of the time versus the textbook C(m,k)/C(n,k) = 4.25% [Prange 62, KT 17]; per-candidate enumeration costs 1.2× the bit-serial baseline; the Gray-scan step costs 2.7× its RAM count. One published claim of ours was wrong and is corrected below (§Corrections).
2. The benchmark's energy model is (up to constants) a known formal model. Charging √a per access to address a is the Hierarchical Memory Model of Aggarwal–Alpern–Chandra–Snir with cost function f(x)=x^α at α = ½ [AACS 87], which the authors themselves motivate as 2-D physical distance — the same argument Dally makes empirically (a 32-bit add costs 20 fJ; fetching its operands from off-chip costs 1.3 nJ — 64,000×) [Dally 22].
3. Does the spatial model change asymptotics? Yes for memory-heavy algorithms, no for the streaming families implemented here. The working rule is E ≈ T·√W (RAM time × root working set). It leaves the exponential terms of enumeration (C(n,k)), Prange ((n/m)^k), and the null-space scan (2^n−m) untouched — polynomial inflation only — but it halves the advantage exponent of the meet-in-the-middle attack (C^1/2 → C^3/4) and, combined with the ISA's lack of data-dependent addressing, prices the memory-rich ISD improvements (MMT, BJMM) out entirely, consistent with Esser–Bellini's estimator findings [EB 22].
4. The compiler (address-assignment rule) is sane but leaves measurable energy on the table. Against the provably optimal static assignment (hottest cell → lowest address, by the rearrangement inequality), the current hand layouts measure 1.41–2.79× over optimal, where the worst assignment would be 3.7–8.6×. A mechanical frequency-sorted reassignment pass closes the static gap for free; phase-aware relocation (software caching, O(1)-competitive by [AACS 87, Thm 5.2]) is the remaining headroom.

The implemented methods and their literature anchors

The benchmark's mask task is exactly syndrome decoding: find the unique weight-k solution of the underdetermined GF(2) system Xw = y (m equations, n unknowns). Sample complexity m ≥ log₂C(n,k) is information-theoretic folklore, stated explicitly in [BGR 20]; the tiers sit at m = ⌈log₂C⌉+1. Worst-case hardness anchors: maximum-likelihood decoding is NP-complete [BMvT 78], minimum distance is NP-hard [Vardy 97]; whether poly time is possible at poly(k log n) samples ("attribute-efficient parity learning") is a long-standing open problem attributed to Blum.

Sanity checks: implementation vs. expectation

Success probabilities

Instruction counts vs. RAM operation counts

The ISA is straight-line (no loops, branches, or indirect addressing), so the honest comparison is circuit instructions vs. bit-serial RAM operations. The overhead factor is not a constant — it tracks how much data-dependent control and addressing each algorithm needs, exactly as the oblivious-computation literature predicts: a data-dependent memory access compiled to cmp/select multiplexing costs O(live cells) per access (the naive RAM→circuit route), where ORAM-style techniques would give Θ(log N) and fully oblivious algorithms O(1) [PF 79, GO 96, AKLNPS 20].

Everything is where the theory puts it; nothing needed fixing in the circuits. What did need fixing is two of our published claims — see §Corrections. Wall-clock context: evaluating one circuit over a 1,024–2,048-instance suite takes 0.5–5 s on an M-series laptop (batched numpy engine, ~1.5 B instruction-instances/s); a fresh-randomness adjudication run including suite generation stays under a minute.

The spatial model, formally

The benchmark charges ⌈√a⌉ per operand read of address a and nothing for arithmetic. Two independent lines of work say this is the right first-order model:

• Empirical (Dally). Data movement, not arithmetic, dominates energy: 20 fJ for a 32-bit add vs 1.3 nJ to fetch its operands from DRAM (64,000×); ~1.9 pJ per 64 bits per mm on-chip; and a 256 MB on-chip memory access costs 58 pJ of which 57.4 pJ is wire traversal. His proposed fix to PRAM — give every datum a location and charge Manhattan distance — is this benchmark's model with arithmetic kept at unit cost [Dally 22]. A memory of capacity S laid out in 2-D has side Θ(√S), hence √-in-address pricing.
• Formal (HMM). The Hierarchical Memory Model prices access to address x at f(x); the polynomial case f(x)=x^α is analyzed in [AACS 87, Thm 4.1], and the authors explicitly note a memory level of 2^ℓ cells sits 2^ℓ/2 away in 2-D. At α = ½ (our model): scanning N inputs costs Θ(N^3/2); sorting and FFT are also Θ(N^3/2) (scan-dominated — the log factors vanish); binary search collapses from log N to Θ(√N); and α = ½ is precisely the critical exponent at which cubic linear algebra turns movement-bound: matmul is Θ(n³) for α<½, Θ(n³log n) at α=½, Θ(n^2α+2) above. Any time-T, space-S RAM computation costs at most T·√S, and their threshold identity T_f = Σ_m Δf(m)·T_m converts red–blue-pebbling I/O lower bounds [HK 81] into distance-priced lower bounds.

Does the spatial model change the cost asymptotically?

The operational law is E ≈ T·√W: RAM operation count times the square root of the live working set (exact when accesses spread uniformly over W; better when frequencies are skewed and the layout exploits it). The measured mean read costs confirm it: the GE phase, whose working set is the ~1,500-cell matrix+tables region, averages 39.3 energy/read (√1500 ≈ 39); the scan phase, hot on a ~500-cell state, averages 10.6; streaming enumeration averages 9.0.

Answer: the spatial model does not change the asymptotic cost of the three streaming families implemented in this benchmark — their exponential terms survive intact, inflated by working-set polynomials — but it does change asymptotics wherever an algorithm buys time with memory: time–space tradeoffs shift toward less memory, table-based attacks lose half their exponent advantage, and the erasure is compounded by the straight-line ISA making hashing inexpressible. This is the model behaving as designed: it is an energy model, and memory is distance.

Lower bounds

RAM model

Unconditional: only the trivial Ω(nm) (the solver must examine the instance; for exact recovery on all identifiable instances an adversary can hide the distinguishing bits in unread cells). Conditional: worst-case NP-hardness [BMvT 78, Vardy 97]; average-case, the best known algorithms bracket the truth between Õ(C(n,k/2)) [KS 06] and C(n,k)·m, with n^Ω̃(k) lower bounds for the noisy variant under dense-LPN assumptions [BBTV 24]; poly-time at m = poly(k log n) samples is open.

Spatial model

Three floors, in increasing strength:

1. Input residence. Reading any R distinct cells costs at least Σ_i≤R√i ≈ ⅔R^3/2 under the best possible placement. Reading the whole instance (nm+m = 594 cells at n=32) floors at ≈ 9.7k energy — negligible against measured costs of 1.5–43M, so input locality is not what binds at benchmark sizes.
2. Working-set floor. Any GE-style computation keeping an m×n live matrix pays Θ(√(mn)) per matrix access on average; via the HMM threshold identity, Hong–Kung-style I/O bounds for linear algebra lift to √-priced bounds [AACS 87, HK 81]. This is the binding term for the implemented decoders (measured 19–39 energy/read).
3. Conditional. Any super-polynomial RAM lower bound transfers: spatial cost ≥ RAM reads (every read costs ≥1), so the conjectured n^Ω̃(k) hardness carries over verbatim, and the spatial model can only raise it.

The compiler: is the address-assignment rule sensible?

"Compiler" here = the rule assigning each logical register to a memory address. For a fixed straight-line program the optimal static assignment is a closed-form: sort cells by total read count and assign addresses in that order (if f₁≥f₂ and c₁≤c₂, any assignment pairing f₁ with c₂ is improved by swapping — the rearrangement inequality). We computed this optimum exactly for each circuit from its read-frequency profile:

Reading the table: the hand layouts (hot scratch at low addresses) capture most of the assignment win — 1.4–2.8× from optimal where the worst ordering would sit 3.7–8.6× — and the sweep-dominated circuits (full scan, enumeration) are closest to optimal because their hottest cells were placed first by design. The 2.8× ISD gap has a concrete cause: the M matrix occupies addresses 1–594 while the small pivoting registers, read ~7× per row per column, sit above it; frequency-sorted reassignment would move ~30 scratch cells below the matrix. The scan's per-phase energy split shows the same structure — scan-state 15.2M, Gray-basis tables 6.0M, RREF matrix region 7.8M, raw-basis tables 9.6M, inputs 0.03M — the precompute tables are cold at scan time but were priced as if permanent.

Verdict and headroom. The current rule is sensible (measurably better than order-of-declaration, within ~2× of static-optimal) and three mechanical improvements remain, in order of effort: (1) a frequency-sorted reassignment pass — compile, count reads per cell, permute addresses, re-emit; closes the static gap to 1.0 at zero algorithmic cost; (2) phase-aware address reuse — the RREF phase wants the matrix at address 1, the scan phase wants its state there; since cells are overwritable, a compiler can relocate between phases (copies cost energy, but AACS's Block-LRU theorem [AACS 87, Thm 5.2] says dynamic placement is O(1)-competitive with the offline optimum — static single assignment is not); (3) packing — 8 bits per byte cell divides both reads and the working set, compounding as ~8×·√8. For the large-scale (10M-instruction) examples the same rules apply unchanged; the assignment problem stays linear-time (sort by frequency), so compiler cost is not a scaling concern.

Corrections to previously published claims

• "ISD per-restart success is 1.8%, rank deficiency bites harder at k=5" — wrong, now corrected. The 1.8% was a single deterministic dev-suite draw; success is strongly secret-dependent under fixed rotating information sets, so per-suite recovery ranges 2.2–5.6%. Pooled over fresh randomness the rate is 4.22%, matching the idealized Prange ratio (4.25%). The genuine rank-deficiency correction is visible at n=12 (measured 19.2% vs ideal 25.45%, consistent with the 0.289/0.578/0.128 corank law [Kolchin 99]) but washes out at n=32 full-width pivoting. The main report's tier-2 section has been updated.
• "Straight-line instruction count ≈ RAM ops × 2–7" — too narrow. The measured band across implemented methods is 1.2× (enumeration) to 17.8× (basis extraction), and the upper end is not slack but the predicted O(live-cells)-per-dynamic-access multiplexer cost. The main report's "Why 10⁶ instructions" section has been updated to 1.2–18×.

References

1. E. Prange. The use of information sets in decoding cyclic codes. IRE Trans. Information Theory IT-8(5):S5–S9, 1962.
2. G. Kachigar, J.-P. Tillich. Quantum information set decoding algorithms. PQCrypto 2017 (eprint 2017/213), §3.1 — standard Prange analysis form.
3. R. Canto Torres, N. Sendrier. Analysis of information set decoding for a sub-linear error weight. PQCrypto 2016, LNCS 9606, 144–161.
4. D.J. Bernstein, T. Lange, C. Peters. Attacking and defending the McEliece cryptosystem. PQCrypto 2008, LNCS 5299, 31–46 (eprint 2008/318).
5. E. Berlekamp, R. McEliece, H. van Tilborg. On the inherent intractability of certain coding problems. IEEE Trans. IT 24(3):384–386, 1978.
6. A. Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. IT 43(6):1757–1766, 1997.
7. A. Klivans, R. Servedio. Toward attribute-efficient learning of decision lists and parities. JMLR 7:587–602, 2006 — reports Spielman's Õ(n^k/2) meet-in-the-middle algorithm.
8. H. Buhrman, D. García-Soriano, A. Matsliah. Learning parities in the mistake-bound model. IPL 111(1):16–21, 2010.
9. A. Bhattacharyya, A. Gadekar, N. Rajgopal. Improved learning of k-parities. COCOON 2018; TCS 840:249–256, 2020.
10. G. Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. FOCS 2012; J. ACM 62(2), 2015 — n^0.80k for noisy sparse parity.
11. A. Blum, A. Kalai, H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4):506–519, 2003.
12. K. Bangachev, G. Bresler, S. Tiegel, V. Vaikuntanathan. Near-optimal time-sparsity trade-offs for solving noisy linear equations. arXiv:2411.12512, 2024.
13. W. Dally. On the model of computation: Point. CACM 65(9):30–32, 2022 (with U. Vishkin's Counterpoint).
14. A. Aggarwal, B. Alpern, A.K. Chandra, M. Snir. A model for hierarchical memory. STOC 1987, 305–313 — HMM; Thm 4.1 covers f(x)=x^α.
15. J.-W. Hong, H.T. Kung. I/O complexity: the red–blue pebble game. STOC 1981, 326–333.
16. C.D. Thompson. Area–time complexity for VLSI. STOC 1979, 81–88; PhD thesis CMU-CS-80-140, 1980.
17. C. Bouillaguet et al. Fast exhaustive search for polynomial systems in F₂. CHES 2010, LNCS 6225, 203–218.
18. A. Esser, E. Bellini. Syndrome decoding estimator. PKC 2022, LNCS 13177 (eprint 2021/1243).
19. N. Pippenger, M. Fischer. Relations among complexity measures. J. ACM 26(2):361–381, 1979.
20. O. Goldreich, R. Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM 43(3):431–473, 1996.
21. G. Asharov, I. Komargodski, W.-K. Lin, K. Nayak, E. Peserico, E. Shi. OptORAMa: optimal oblivious RAM. EUROCRYPT 2020; J. ACM 2023.
22. V. Kolchin. Random Graphs. Cambridge Univ. Press, 1999, Ch. 3 — corank law for random GF(2) matrices.
23. M. Albrecht, G. Bard, W. Hart. Algorithm 898: efficient multiplication of dense matrices over GF(2). ACM TOMS 37(1), 2010 — M4RI, O(n³/log n).
24. D.E. Knuth. TAOCP Vol. 4A, 2011, §7.2.1.1–7.2.1.3 — Gray codes, revolving-door combinations.