Subset Sum Techniques and Bet on the Error Distribution. As just outlined, our RLPN decoder needs an exponential number \(N = \Theta \left( 1/\varepsilon ^2 \right)\)  of parity-checks of small weight on \(n-s\)  positions.
This can be achieved efficiently by using collision/subset techniques used in the inner loop of ISD's. Recall that all ISD's proceed in two steps, \((i)\)  first they pick an augmented information set and \((ii)\)  then have an inner loop computing low weight codewords of some sort. \((ii)\)  uses advanced techniques to solve subset-sum problems like birthday paradox [1]}, [2]}, Wagner algorithm [3]}, representations techniques [4]}, [5]}. All these techniques can also be used in a natural way in our RLPN decoder to compute the low weight parity-checks we need.
