Robust Inverse Quadratic Error Decay with Meshing and Beam Search for Random Subset Sum
For practitioners working on subset sum problems in cryptography and optimization, this work provides a faster and more accurate algorithm, though it is an incremental improvement over existing meshing techniques.
The paper presents an algorithm for the Random Subset Sum Problem that achieves an expected error of O(B/(n w^2)) using a beam search heuristic with a mesh, running in O(w log w) time. The method is empirically robust across multiple input distributions and establishes a new practical baseline for error decay.
The Subset Sum Problem is a fundamental NP-complete problem in cryptography and combinatorial optimization, with many real-world applications. The Random Subset Sum Problem (RSSP) is a more applicable version of subset sum, where numbers are drawn from some i.i.d input distribution. We present an algorithm that, with probability $1-δ$, constructs the same $O(B/w)$ mesh as Da Cunha et al. (2023), while trimming to $w$ elements throughout and running in $O(w\log w)$ time. Then, we present a novel beam search heuristic running in linearithmic time w.r.t list size $n$ and beam width $w$ using the mesh that gives an expected error of $O\!\left(\frac{B}{nw^2}\right)$ under a standard mean-field assumption with equal standard deviation, demonstrating the practical effectiveness of meshing to achieve error decay. The algorithm is empirically robust to multiple input distributions and can naturally extend to variants with simple changes to the scoring heuristic, establishing a new practical baseline for robust subset sum error decay and $ε$-approximation theory.