Since Prange's seminal work [1]} in 1962, ISD algorithms have played a predominant role for assessing the complexity of
code-based cryptographic primitives. In the fixed rate regime, they have been beaten only once in [2]} with the help of collision techniques, and this only for a tiny code rate range (\(R \in (0.98,1)\) ) and for a short period of time [3]}, [4]} until these collision techniques were merged with the collision techniques to yield modern ISD's. Surprisingly enough, these improved ISD have resulted in decoding complexity curves tilting more and more to the left (i.e. with a maximum which is attained more and more below \(\frac{1}{2}\) ) instead of being symmetric around \(\frac{1}{2}\)  as it could have been expected. It is precisely for rates below \(\frac{1}{2}\)  that RLPN decoding is able to outperform the best ISD's. This seems to point to the fact that it is precisely for this regime of parameters that we should aim for improving them. Interestingly enough, even if there is some room of improvement for RLPN decoding by using better strategies for producing the needed low weight parity-checks, there is a ceiling that this technique can not break (at least if we just split the parity-checks in two parts) and which is
extremely close at rate \(R=0.45\)  to the best ISD algorithm [5]}. The RLPN decoding algorithm presented here has not succeeded in changing the landscape
for very tiny code rates (\(R\)  going to 0), since the complexity exponent of RLPN decoding approaches the one of exhaustive search on codewords, but the speed at which this complexity approaches exhaustive search is much smaller than for ISD's in the full decoding regime (i.e. at the GV distance). The success of RLPN decoding for \(R < 0.3\)  could be traced back precisely to this behavior close to 0. An interesting venue for research could be to try to explore if there are other decoding strategies that would be candidate for beating exhaustive search in the tiny code rate regime.
