Paper 2026/2802

Filtered merges make deeper representation trees pay: Subset Sum and Meet-LWE

Abstract

Dubiner's bucketing codes, used as type-class filters on representation coordinates, let a merge avoid generating matched pairs with the wrong split pattern. We show that in representation trees their main effect is to make depth pay. For random density-one Subset Sum they improve the exponent of Bonnetain, Bricout, Schrottenloher and Shen from 0.2831 (our recomputation) to 0.2690, at depth 5; no better point was found up to depth 9. For May's Meet-LWE on ternary keys they improve the asymptotic exponent by 0.013–0.023 for key weights ω ≥ 0.375. Filters can pay only at merges where most matched pairs have the wrong split pattern, and do pay where such merges bind; we show both where this holds and where it fails. A survival recursion justifies the accounting, a symmetry lemma shows that the filters cannot bias the planted solution, and simulations support the remaining heuristics.