where \(\text{P}_{\text{succ}}\)  is given in Proposition REF . Our only constraints are given by (REF ) and (REF ). By optimizing (REF ) over \(s,u\)  and \(w\) , we can give a lower-bound on the complexity of RLPN decoding. However notice that our lower-bound applies to a partition of parity-checks in two parts (\(s\)  and \(n-s\) ). We do not consider here finer partitions. This method for lower bounding the complexity of RLPN decoding is very similar to the technique used in [1]} to lower bound the complexity of statistical decoding. All in all, we give in Figure REF  this lower-bound of the complexity. The optimal parameters computed for each RLPN algorithms can be found on https://github.com/tillich/RLPNdecoding. As we see our RLPN decoders meet this lower-bound for small rates and we can hope to outperform significantly ISD's for code rates smaller than \(\approx 0.45\) .
<FIGURE>