In the case \(\tau \in [\omega ^\perp ,1/2]\) , \(D\)  is negative,
and
\(K_w^n(t) = \frac{2}{\sqrt{\pi n}} \left(\frac{\tau (1-\tau )}{ -\omega (1-\omega ) D}\right)^{\frac{1}{4}} 2^{\frac{n}{2}(1+h(\omega )-h(\tau ))} \sin (n \theta + \theta _0 + o(1))(1+o(1))\) 
where
\(\theta & = &(\tau -1)\cos ^{-1} \left( \frac{\frac{3}{2}-\omega -\tau }{\sqrt{2(1-\omega )(1-\tau )}} \right)+ \tau \cos ^{-1} \left( \frac{\frac{1}{2}-\omega +\tau }{\sqrt{2\tau (1-\omega )}}\right)+ \omega \cos ^{-1}\left( \frac{1-2 \tau }{b(\omega )}\right) \\\theta _0 & = &\frac{1}{2} \cos ^{-1}\left( \frac{(1-2\tau )(1-2\omega )}{b(\tau )b(\omega )}\right)+ \frac{\pi }{4}\) 
In the zone of zeros of the Krawtchouk polynomials, i.e. when \(\tau \in [\omega ^\perp ,1/2]\) , the Krawtchouk polynomial may take 0 values and it is not clear whether by slightly changing \(w\)  or \(t\) , the behavior of \(\frac{\log _2(K_w^n(t))}{n}\)  would be of the form \(\frac{1+h(\omega )-h(\tau )}{2} + o(1)\) . This is actually the case, since we can use
[[1]}]
Between any two consecutive roots of \(K^n_{w}\) , where \(1 \le w \le \frac{n}{2}\) , there exists \(\ell \)  such that:
\(\frac{\log _2(K_w^n(\ell ))}{n} = \frac{1+h(\omega )-h(\lambda )}{2} + o(1), \;\;\text{where $\omega \mathop {=}\limits ^{\triangle }\frac{w}{n}$ and $\lambda \mathop {=}\limits ^{\triangle }\frac{\ell }{n}$.}\) 

We also know that
[[1]}, [3]}]
For all \(w \in \llbracket 1,n \rrbracket \) , \(K^n_w\)  has \(w\)  distinct zeros, all in \(\left[n \omega ^\perp , n(1-\omega ^\perp )\right]\)  where \(\omega ^\perp \mathop {=}\limits ^{\triangle }\frac{1}{2}-\sqrt{\omega (1-\omega )}\)  and \(\omega \mathop {=}\limits ^{\triangle }\frac{w}{n}\) . The smallest root is at distance \(o(n)\)  from
\(n \omega ^\perp \) , the largest at distance \(o(n)\)  from \(n(1-\omega ^\perp )\) . The distance between any two consecutive roots
is \(o(n)\) .

By using these two lemmas, we readily obtain
[exponential behavior of \(\delta ^2\) ]
Let \(\tau \)  and \(\omega \)  be two reals in the interval \(\left[0,\frac{1}{2}\right]\) . Let \(\omega ^\perp \mathop {=}\limits ^{\triangle }\frac{1}{2}-\sqrt{\omega (1-\omega )}\)  and \(z \mathop {=}\limits ^{\triangle }\frac{1-2\tau - \sqrt{D}}{2 (1-\omega )}\)  where
\(D \mathop {=}\limits ^{\triangle }\left(1- 2 \tau \right)^2-4 \omega (1-\omega )\) . There exists a sequence of positive integers
\((t_n)_{n \in \mathbb {N}}\)  and \((w_n)_{n \in \mathbb {N}}\) , such that \(\frac{t_n}{n} \mathop {\rightarrow }\limits _{n \rightarrow \infty } \tau \) ,
\(\frac{w_n}{n} \mathop {\rightarrow }\limits _{n \rightarrow \infty } \omega \)  and
\(\frac{\log _2(K_{w_n}^n(t_n)^2/\binom{n}{w_n}^2)}{n}\)  has a limit which we denote \(\tilde{\delta }(\tau ,\omega )\)  with
\(\tilde{\delta }(\tau ,\omega ) = \left\lbrace \begin{array}{ll}2 \left(\tau \log _2(1-z)+ (1-\tau ) \log _2(1+z) - \omega \log _2 z - h(\omega )\right) & \mbox{ if } \tau \in [0,\omega ^\perp ] \\1 - h(\tau )-h(\omega ) & \mbox{ otherwise.}\end{array}\right.\) 


In the case \(\tau \in [0,\omega ^\perp ]\)  we just let \(t_n = \lceil \tau n\rceil \) , \(w_n = \lceil \omega n\rceil \)  and use directly the asymptotic expansion
(REF ). In the case \(\tau \in \left[\omega ^\perp ,\frac{1}{2}\right]\)  we still define \(w_n\)  with \(w_n \mathop {=}\limits ^{\triangle }\lceil \omega n\rceil \)  but define \(t_n\)  differently. For \(n\)  large enough, we know from Lemma REF  that \(\lceil \tau n\rceil \)  lies between two zeros of the Krawtchouk polynomial and that there exists an integer \(t_n\)  in this interval such that
\(\frac{\log _2(K_{w_n}^n(t_n))}{n} = \frac{1+h(\omega )-h(\tau _n)}{2} + o(1)\) 
where \(\tau _n = \frac{t_n}{n}\) . Now since the size of this interval is an \(o(n)\)  we necessarily have \(\tau _n=\tau +o(1)\)  and therefore
\(\frac{\log _2(K_{w_n}^n(t_n))}{n} = \frac{1+h(\omega )-h(\tau )}{2} + o(1).\)
The point of this proposition is that the term \(2 \log _2(K_w^{n-s}(u)/\binom{n-s}{w})\)  quantifies the exponential behavior of the square \(\varepsilon ^2\)  of the bias \(\varepsilon \)  (see Lemma REF ) and \(1/\varepsilon ^2\)  is up to polynomial terms the number of parity-checks we need for having enough information to solve the LPN problem as will be seen. This is because the capacity of the BSC\((\frac{1 - \varepsilon }{2})\)  is \(1 - h\left( \frac{1 - \varepsilon }{2}\right)=\theta (\varepsilon ^2)\)  and that solving an LPN-problem with a secret of size \(s\)  and \(N\)  samples amounts to be able to decode a random linear code of rate \(\frac{s}{N}\)  over the BSC\((\frac{1 - \varepsilon }{2})\) . It is therefore doable as soon as the rate is below the capacity (see Theorem REF ). The reason why the Shannon capacity appears here is because of the following heuristic/assumption we will make here:
[LPN modelling]
We will assume that the \(\left\langle {\mathbf {e}}_{{N}} , {\mathbf {h}}_{{N}} \right\rangle \)  are i.i.d Bernoulli random variables of parameter \(\frac{1-\varepsilon }{2}\) .
Strictly speaking, the corresponding random variables are not independent, however we have performed extensive simulations showing that indeed decoding the corresponding code behaves similarly to this model. Some experiments with the programs that have been used for running them can be found on https://github.com/tillich/RLPNdecoding. Note that similar heuristics are also used to analyze a related lattice decoder making use of short dual lattice vectors (they are called dual attacks in the literature).
With Assumption REF , the number \(N\)  of LPN samples is such that \(s/N = O(\varepsilon ^2)\)  for a small enough constant in the \(O\) , performing maximum-likelihood decoding of the corresponding \([N,s]\)  binary code recovers the secret \({\mathbf {e}}_{{P}}\)  with probability \(1-o(1)\) .
Performing maximum likelihood decoding of the corresponding code can be achieved by a fast Fourier transform on a relevant vector. Indeed, for a given received word \({\mathbf {y}}\)  and a set \(\widetilde{{{H}}}\)  of \(N\)  parity-checks so that their restriction to \({{P}}\)  leads to a set \({{H}}\)  of \(N\)  different vectors of \(\mathbb {F}_2^s\) , we let for \({\mathbf {a}}\in {{H}}\) , \(\widetilde{{\mathbf {a}}}\)  be the unique parity-check in \(\widetilde{{{H}}}\)  such that \(\widetilde{{\mathbf {a}}}_{{{P}}}={\mathbf {a}}\)  and define \(f_{{\mathbf {y}},{{H}}}\)  as
\(f_{{\mathbf {y}},{{H}}}: \mathbb {F}_2^s & \rightarrow & \mathbb {R}\nonumber \\{\mathbf {a}}& \mapsto & \left\lbrace \begin{array}{ll} (-1)^{\left\langle {\mathbf {y}} , \widetilde{{\mathbf {a}}} \right\rangle }\; & \text{ if ${\mathbf {a}}\in {{H}}$} \\ 0 & \text{ otherwise} \end{array} \right.\) 
We define the Fourier transform of such a function by
\(\widehat{f}({\mathbf {x}}) \mathop {=}\limits ^{\triangle }\sum _{{\mathbf {u}}\in \mathbb {F}_2^s} f({\mathbf {u}}) (-1)^{\left\langle {\mathbf {x}} , {\mathbf {u}} \right\rangle }.\) 
The code \({D}\)  we want to decode (obtained via our LPN samples) is described as
\({D}\mathop {=}\limits ^{\triangle }\lbrace {\mathbf {c}}_{{\mathbf {x}}},\;{\mathbf {x}}\in \mathbb {F}_2^s \rbrace  \;\;\text{where} \;\;{\mathbf {c}}_{{\mathbf {x}}} \mathop {=}\limits ^{\triangle }(\left\langle {\mathbf {x}} , {\mathbf {a}} \right\rangle )_{{\mathbf {a}}\in {{H}}}, \) 
and the word \({\mathbf {u}}_{{\mathbf {y}},{{H}}}\)  we want to decode is given by
\({\mathbf {u}}_{{\mathbf {y}},{{H}}}=(\left\langle {\mathbf {y}} , \widetilde{{\mathbf {a}}} \right\rangle )_{{\mathbf {a}}\in {{H}}}.\) 
It is readily seen that
\(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}}) & = & \sum _{{\mathbf {a}}\in \mathbb {F}_2^s} f({\mathbf {a}}) (-1)^{\left\langle {\mathbf {x}} , {\mathbf {a}} \right\rangle }\\& = & \sum _{\begin{array}{c}{\mathbf {a}}\in {{H}}\end{array}} (-1)^{\left\langle {\mathbf {x}} , {\mathbf {a}} \right\rangle +\left\langle {\mathbf {y}} , \tilde{{\mathbf {a}}} \right\rangle }\\& = & \#{{H}}- 2 |{\mathbf {u}}_{{\mathbf {y}},{{H}}}-{\mathbf {c}}_{{\mathbf {x}}}|,\) 
In other words, finding the closest codeword to \({\mathbf {u}}_{{\mathbf {y}},{{H}}}\)  is nothing but finding the \({\mathbf {x}}\)  which maximizes \(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}})\) .
This is achieved in time \(\mathop {}\mathopen {}O\mathopen {}\left(s2^s\right)\)  by performing a fast Fourier transform. Notice that an exhaustive search would cost \(\mathop {}\mathopen {}O\mathopen {}\left(2^{2s}\right)\) .
Sketch of the whole algorithm
[h!]
RLPN decoder
 Input: \({\mathbf {y}}\) , \(t\) , \( an \) [n,k ]\(-code\\\hspace*{0.0pt} \textbf {Output:} \) e\( such that \) |e|=t\( and \) y- e.

RLPNdecode\({\mathbf {y}}\) , \(, \) t\(\) 
\(s, u \leftarrow {Optim}{t,\;k,\;n}\) 
\(s\)  and \(u\)  in order to minimize the complexity of the following procedure.
\(i\)  from 1 to \(\text{N}_{\text{iter}}\) 
\(\text{N}_{\text{iter}}\)  is a certain function of \(n\) , \(s\) , \(t\)  and \(u\) .
\({{P}}\stackrel{\$}{\leftarrow } \left\lbrace {{I}}\subseteq \llbracket 1, n \rrbracket \ : \ \#{{I}}= s\right\rbrace \) 
\({{N}}\leftarrow \llbracket 1, n \rrbracket \setminus {{P}}\) 
\({{H}}\leftarrow \)  Create\(N,w,{{P}}\) 
\(\widehat{f_{{\mathbf {y}},{{H}}}}\leftarrow \) FFT\(f_{{\mathbf {y}},{{H}}}\) 
\({\mathbf {x}}_0 \leftarrow \arg \max \widehat{f_{{\mathbf {y}},{{H}}}}\) 
\(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}}_0) \ge \frac{\delta N}{2}\)  \(\delta \mathop {=}\limits ^{\triangle }{K_{w}^{n-s}(u)}/{\binom{n-s}{w}}\) .
\({\mathbf {e}}\)  such that \({\mathbf {e}}_{{{P}}} = {\mathbf {x}}_0\)  and \({\mathbf {e}}_{{{N}}} = {RLPNdecode}{{\mathbf {y}}_{{{N}}},{{{N}}},t - \left|{\mathbf {x}}_0\right|})\)
Besides, the fast Fourier transform solving the LPN problem, Algorithm REF  uses two other ingredients:

A routine Create\(N,w,{{P}}\)  creating a set \({{H}}\)  of \(N\)  parity-check equations \({\mathbf {h}}\)  such that \(|{\mathbf {h}}_{{N}}|=w\)  where \({{N}}\mathop {=}\limits ^{\triangle }\llbracket 1, n \rrbracket \setminus {{P}}\) .
We will not specify how this function is realized here: this is done in the following sections. This procedure together with an FFT for decoding the code associated to the parity-check equations in \({{H}}\)  (see Equation (REF )) form the inner loop of our algorithm.

An outer loop making a certain number \(\text{N}_{\text{iter}}\)  of calls to the inner procedure, checking each time a new set \({{P}}\)  of \(s\)  positions with the hope of finding an \({{N}}\)  containing an unusually low number \(u\)  of errors in it. The point is that with a right \(u\) , the number of times we will have to check a new \({{P}}\)  is outweighed by the decrease in \(N\)  because the bias \(\delta \)  is much higher for such a \(u\) .


Analysis of the RLPN decoder
We need to show now that our RLPN decoder returns what we expect.
[acceptation criteria]
Under Assumption REF ,
by choosing \(N_{\mathrm {iter}} = \omega \left(\frac{1}{\text{P}_{\text{succ}}}\right)\) , \(s = \omega (1)\)  and \(N = \omega \left( \frac{n}{\delta ^2}\right)\) ,
we have with probability \(1 - \mathop {}\mathopen {}o\mathopen {}\left(1\right)\)  that at least one iteration is such that \({\mathbf {e}}_{{{P}}}\)  meets the acceptation criteria \(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {e}}_{{{P}}}) \ge \frac{\delta N}{2}\) . Moreover, the probability that there exists \({\mathbf {x}}\ne {\mathbf {e}}_{{{P}}}\)  which meets this acceptation criteria is \(o(1)\) .
We need to show that two things happen both with probability \(1-o(1)\) :
(i) there is at least one iteration in the Algorithm REF  for which \(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {e}}_{{{P}}}) \ge \frac{\delta N}{2}\)
(ii) for all \({\mathbf {x}}\in \mathbb {F}_2^s\)  different from \({\mathbf {e}}_{{{P}}}\) , we have \(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}}) < \frac{\delta N}{2}\)  for all iterations.
(i) The first point follows from the fact that by taking \(\text{N}_{\text{iter}}\mathop {=}\limits ^{\triangle }\omega \left(\frac{1}{\text{P}_{\text{succ}}}\right)\) , we have that one iteration is such that \(\left|{\mathbf {e}}_{{{N}}}\right| = u\)  and \(\left|{\mathbf {e}}_{{{P}}}\right| = t - u\)  with probability \(1 - \mathop {}\mathopen {}o\mathopen {}\left(1\right)\) . For such an iteration, we have from Assumption REF  that \(\left| {\mathbf {c}}_{{\mathbf {e}}_{{{P}}}} - {\mathbf {u}}_{{\mathbf {y}},{{H}}} \right| \sim \mathrm {Binomial}\left(N, \frac{1 - \varepsilon }{2}\right)\) . Thus, by using the Hoeffding inequality, we have:
\(\operatorname{{\mathbb {P}}}\left(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {e}}_{{{P}}}) \ge \frac{\delta N}{2} \right) & = & \operatorname{{\mathbb {P}}}\left(\left| {\mathbf {c}}_{{\mathbf {e}}_{{{P}}}} - {\mathbf {u}}_{{\mathbf {y}},{{H}}} \right| \le \frac{1-\frac{\delta }{2}}{2} N\right) \\& \ge & 1 - \exp \left( - \frac{(\varepsilon -\delta /2)^2 N}{2}\right)\) 
By the choice made on \(N\)  this quantity is \(1-o(1)\) .
(ii) For the second point, consider now an \({\mathbf {x}}\in \mathbb {F}_2^s\)  such that \({\mathbf {x}}\ne {\mathbf {e}}_{{{P}}}\) . Let \({\mathbf {c}}^{\prime } \mathop {=}\limits ^{\triangle }{\mathbf {c}}_{{\mathbf {x}}} - {\mathbf {c}}_{{\mathbf {e}}_{{{P}}}}\) , \(d \mathop {=}\limits ^{\triangle }\left|{\mathbf {c}}^{\prime }\right|\)  and \({\mathbf {y}}^{\prime } \mathop {=}\limits ^{\triangle }{\mathbf {u}}_{{\mathbf {y}},{{H}}} - {\mathbf {c}}_{{\mathbf {e}}_{{{P}}}}\) . Then we have :
\(\operatorname{{\mathbb {P}}}\left(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}}) \ge \frac{\delta N}{2} \right) & = & \operatorname{{\mathbb {P}}}\left(\left| {\mathbf {c}}^{\prime } - {\mathbf {y}}^{\prime } \right| \le \frac{1 - \frac{\delta }{2}}{2} N \right) \;\;\text{(because $|{\mathbf {c}}_{\mathbf {x}}-{\mathbf {u}}_{{\mathbf {y}},{{H}}}|=|{\mathbf {c}}^{\prime }-{\mathbf {y}}^{\prime }|$)} \nonumber \\& = & \sum _{b = 0}^{N} \sum _{a=0}^{\frac{1 - \frac{\delta }{2}}{2} N }\operatorname{{\mathbb {P}}}\left( \left| {\mathbf {c}}^{\prime } - {\mathbf {y}}^{\prime } \right| = a \ \Big \vert \ \left|{\mathbf {y}}^{\prime }\right| = b \right) \cdot \operatorname{{\mathbb {P}}}\left( \left|{\mathbf {y}}^{\prime }\right| = b \right) \nonumber \\& \le & \sum _{b = 0}^{N} \sum _{a=0}^{\frac{1 - \frac{\delta }{2}}{2} N } \operatorname{{\mathbb {P}}}_{{\mathbf {y}}^{\prime }}\left( \left| {\mathbf {c}}^{\prime } - {\mathbf {y}}^{\prime } \right| = a \ \Big \vert \ \left|{\mathbf {y}}^{\prime }\right| = b \right) \nonumber \\& \le & \sum _{b = 0}^{N} \sum _{a=0}^{\frac{1 - \frac{\delta }{2}}{2} N } \frac{\binom{b}{\frac{d+b-a}{2}} \binom{N - b}{\frac{d-b+a}{2}}}{\binom{N}{d}}. \) 
The last point follows from the fact that \(|{\mathbf {y}}^{\prime }| \sim \mathrm {Binomial}\left(N, \frac{1 - \varepsilon ^{\prime }}{2}\right)\)  for some \(\varepsilon ^{\prime }\)  depending on \(|{\mathbf {e}}_{{{N}}}|\)  and therefore the conditional distribution of \({\mathbf {y}}^{\prime }\)  given that \(|{\mathbf {y}}^{\prime }|=b\)  is the uniform distribution of words of weight \(b\)  over \(\mathbb {F}_2^N\) . This implies
\(\operatorname{{\mathbb {P}}}_{{\mathbf {y}}^{\prime }}\left( \left| {\mathbf {c}}^{\prime } - {\mathbf {y}}^{\prime } \right| = a \ \Big \vert \ \left|{\mathbf {y}}^{\prime }\right| = b \right) = \frac{\binom{b}{\frac{d+b-a}{2}} \binom{N - b}{\frac{d-b+a}{2}}}{\binom{N}{d}}.\) 
Note that both \({\mathbf {c}}_{{\mathbf {x}}}\)  and \({\mathbf {c}}_{{\mathbf {e}}_{{{P}}}}\)  are in the code \({D}\)  defined by Equation (REF ). We can bound again the (typical) minimum nonzero weight and the maximum weight by using [4]}.
Let \({{B}}= \lbrace {\mathbf {x}}\in \mathbb {F}_2^N: 0 < |{\mathbf {x}}| \le N h^{-1}(1-2s/N)\rbrace \) . The expected number \(M\)  of codewords of \({D}\)  in \({{B}}\)  is \(\frac{\#{{B}}}{2^{N(1-s/N)}}\) .
Since \(\#{{B}}\le 2^{Nh(h^{-1}(1-2s/N))}=2^{N(1-2s/N)}\)  we have that \(M \le 2^{-s}\) . Since the probability that the minimum distance of
\({D}\)  is less than or equal to \(N h^{-1}(1-2s/N)\)  is upper-bounded by \(M\) , we obtain that the minimum distance of \({D}\)  is greater than
\(N h^{-1}(1-2s/N)\)  with probability \(1-o(1)\) . A similar reasoning can be made for the maximum weight. We therefore obtain that with probability
\(1-o(1)\)  all the weights \(d\)  of the non-zero codewords of \({D}\)  lie in \(\left.d^-, d^+ \right.\)  where
\(d^- & \mathop {=}\limits ^{\triangle }& Nh^{-1}(1-2s/N)\\d^{+} & \mathop {=}\limits ^{\triangle }& N - Nh^{-1}(1-2s/N).\) 
In such a case, we always have for \(n\)  large enough
\(a \le & d &\le N-a \\1-2s/N \le &h(d/N) & \le 1.\) 
We observe now that
\(\frac{\binom{b}{\frac{d+b-a}{2}} \binom{N - b}{\frac{d-b+a}{2}}}{\binom{N}{d}} & \le & 2^{b h\left( \frac{1}{2} - \frac{d - a}{2b}\right) + (N - b) h\left( \frac{1}{2} - \frac{N - d - a}{2(N-b)}\right) - N h\left( \frac{d}{N}\right)} \;\;\text{(because of (\ref {eq:d}))} \nonumber \\& \le &2^{ \min \left[ - b \left( 1 - h\left( \frac{1}{2} - \frac{d - a}{2b}\right)\right) + 2s \ , \ -(N - b) \left( 1 - h\left( \frac{1}{2} - \frac{ d - a}{2(N-b)}\right)\right) + 2s \right] } \;\;\text{(because of (\ref {eq:hdN}))} \nonumber \\& \le & 2^{-\frac{N}{2} \left( 1 - h\left( \frac{1}{2} - \frac{d - a}{2N}\right)\right) + 2s} \) 
The last inequality comes from the fact that either \(b\)  or \(N-b\)  is greater than \(\frac{N}{2}\)  and that both of them are smaller than \(N\) .
Since \(h^{-1}(1-u) = \frac{1}{2}-\Theta \left( \sqrt{u} \right)\)  for \(u \rightarrow 0^+\)  we have that
\( N/2(1- \Theta \left( \sqrt{\frac{s}{N}} \right)) \le d \le N/2(1+ \Theta \left( \sqrt{\frac{s}{N}} \right))\)  and
therefore
\(\frac{d-a}{2N} \ge \frac{\delta /2-\Theta \left( \sqrt{\frac{s}{N}} \right)}{4} = \Omega \left( \delta  \right).\) 
By using that \(h(1/2-u)=1-\Theta \left( u^2 \right)\)  for \(u \rightarrow 0\)  together with (REF ) in (REF ) we obtain
\(\frac{\binom{b}{\frac{d+b-a}{2}} \binom{N - b}{\frac{d-b+a}{2}}}{\binom{N}{d}} \le 2^{-\Omega \left( N\delta ^2 \right)+2s}.\) 
By plugging this inequality in (REF ) we finally obtain
\(\operatorname{{\mathbb {P}}}\left(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}}) \ge \frac{\delta N}{2} \right) \le N^2 2^{-\Omega \left( N\delta ^2 \right)+2s}\) 
and the probability of the event “there exists an iteration and an \({\mathbf {x}}\ne {\mathbf {e}}_{{P}}\)  such that \(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}}) \ge \frac{\delta N}{2}\) ”
is upperbounded by
\(N_{\text{iter}} 2^s N^2 2^{-\Omega \left( N\delta ^2 \right)+2s} = o(1).\) 
The space and time complexity of this method are readily seen to be given by


Assume that Create\(N\) ,\(w\) ,\({{P}}\)  produces \(N\)  parity-check equations in space \(\text{S}_{\text{eq}}\)  and time
\(\text{T}_{\text{eq}}\) . The probability \(\text{P}_{\text{succ}}\)  (over the choice of \({{N}}\) ) that there are exactly \(u\)  errors in \({{N}}\)  is given by
\(\text{P}_{\text{succ}}= \frac{\binom{s}{t-u}\binom{n-s}{u}}{\binom{n}{t}}.\)  The space complexity \(S\)  and the time complexity \(T\)  of the RLPN-decoder are given by
\(\textbf {\textup {Space:}}\;\; S=\mathop {}\mathopen {}O\mathopen {}\left(\text{S}_{\text{eq}}+2^s\right), \quad \textbf {\textup {Time:}}\;\; T = \mathop {}\mathopen {}\widetilde{O}\mathopen {}\left(\frac{\text{T}_{\text{eq}}+2^s}{\text{P}_{\text{succ}}}\right).\) 
The parameters \(s\) , \(u\)  and \(w\)  have to meet the following constraints
\(N & \le & 2^s \\N & \le & \frac{\binom{n-s}{w}}{2^{k-s}}.\) 
The algorithm outputs the correct \({\mathbf {e}}_{{P}}\)  with probability \(1-o(1)\)  if in addition we choose \(N\)  and
\(\text{N}_{\text{iter}}\)  such that
\(N &= &\omega \left(n \left(\frac{\binom{n-s}{w}}{K_w^{n-s}(u)}\right)^2 \right) \\\text{N}_{\text{iter}}& =& \omega \left(\frac{1}{\text{P}_{\text{succ}}}\right). \) 


All the points are straightforward here, with the exception of the constraints. The first constraint is that the number of parity-checks should not be bigger than the total number of different LPN samples we can possibly produce. The second one is that the number of parity-checks needed is smaller than the number of available parity-checks.
The conditions ensuring the correctness of the algorithm follow immediately from Proposition REF .
The proof of the correctness of the algorithm relies on the validity of the LPN modeling (Assumption REF ). We have programmed this algorithm and have verified that for several parameters that it really behaves as predicted. The corresponding experiments with the programs that have been used for running them can be found on https://github.com/tillich/RLPNdecoding.

Using several independent LPN samples \(\left\langle {\mathbf {a}} , {\mathbf {e}}_{{P}} \right\rangle  + e\)  with the same \({\mathbf {a}}\)
It can be noticed that when \(N\)  is large enough, we may actually have several different parity-checks \({\mathbf {h}}\)  which collide on \({{P}}\) , i.e. lead to the same \({\mathbf {h}}_{{P}}\) . This leads to different LPN samples \(\left\langle {\mathbf {a}} , {\mathbf {e}}_{{P}} \right\rangle  + e\)  with the same \({\mathbf {a}}\) . A simple way to deal with this would be simply to keep just one of them. However, there is a much better way to deal with this issue, which is to use them to decrease the LPN noise. It uses the following lemma, which is for instance one of the two main ingredients used for decoding LDPC codes.
[[5]}]
Assume that we are given \({\mathbf {a}}\in \mathbb {F}_2^s\)  and \(M\)  LPN samples
\(y_i=\left\langle {\mathbf {a}} , {\mathbf {s}} \right\rangle +e_i\)  where the \(e_i\) 's are independent and \(p_i\mathop {=}\limits ^{\triangle }\operatorname{{\mathbb {P}}}(e_i=1)\) . \({\mathbf {s}}\)  is distributed uniformly at random in \(\mathbb {F}_2^s\) .
Define \(p^{\prime }_i\mathop {=}\limits ^{\triangle }p_i\)  if \(y_i=0\)  and \(p^{\prime }_i \mathop {=}\limits ^{\triangle }1-p_i\)  otherwise.
Then
\(\operatorname{{\mathbb {P}}}(\left\langle {\mathbf {a}} , {\mathbf {s}} \right\rangle =1) = \frac{\prod _{i=1}^M p^{\prime }_i}{\prod _{i=1}^M p^{\prime }_i+\prod _{i=1}^M (1- p^{\prime }_i)}.\) 

This allows to obtain a finer information on \(\left\langle {\mathbf {a}} , {\mathbf {s}} \right\rangle \) . We let \(p({\mathbf {a}})\)  be the probability obtained in (REF ). We define now
\(f_{{\mathbf {y}},{{H}}}\)  slightly differently by
\(f_{{\mathbf {y}},{{H}}}: \mathbb {F}_2^s & \rightarrow & \mathbb {R}\nonumber \\{\mathbf {a}}& \mapsto & \left\lbrace \begin{array}{ll}\log \left( \frac{1-p({\mathbf {a}})}{p({\mathbf {a}})}\right)\; & \text{ if ${\mathbf {a}}\in {{H}}$} \\ 0 & \text{ otherwise} \end{array} \right. \) 
A straightforward computation leads now to
\(\widehat{f_{{\mathbf {y}},{{H}}}}({\mathbf {x}}) & = & \sum _{{\mathbf {a}}\in \mathbb {F}_2^s} f({\mathbf {a}}) (-1)^{\left\langle {\mathbf {x}} , {\mathbf {a}} \right\rangle }\\& = & \sum _{{\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =0} \log \left( \frac{1-p({\mathbf {a}})}{p({\mathbf {a}})} \right) + \sum _{ {\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =1} \log \left( \frac{p({\mathbf {a}})}{1-p({\mathbf {a}})}\right) \\& = & \log \left(\prod _{{\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =0} \frac{1-p({\mathbf {a}})}{p({\mathbf {a}})} \prod _{{\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =1} \frac{p({\mathbf {a}})}{1-p({\mathbf {a}})}\right)\\& = & \log \left(\frac{\left( \prod _{{\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =0} (1-p({\mathbf {a}})) \prod _{{\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =1} p({\mathbf {a}})\right)^2}{\underbrace{\prod _{{\mathbf {a}}\in {{H}}} p({\mathbf {a}})(1-p({\mathbf {a}}))}_{\text{constant}}} \right)\) 
It is readily seen that since the function \(x \mapsto \log x^2\)  is increasing and that the denominator \(\prod _{{\mathbf {a}}\in {{H}}} p({\mathbf {a}})(1-p({\mathbf {a}})\)  does not depend on \({\mathbf {x}}\) ,
the \({\mathbf {x}}\)  maximizing this quantity is precisely the \({\mathbf {x}}\)  which maximizes the quantity
\(g({\mathbf {x}}) \mathop {=}\limits ^{\triangle }\prod _{{\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =0} (1-p({\mathbf {a}})) \prod _{{\mathbf {a}}\in {{H}}, \left\langle {\mathbf {a}} , {\mathbf {x}} \right\rangle =1} p({\mathbf {a}})\) 
which in turn is clearly the maximum-likelihood candidate. In other words, we just have to replace
in Algorithm REF  the function \(f_{{\mathbf {y}},{{H}}}\)  with this new definition. It remains to understand how the necessary number of needed parity-check equations evolves. This is done through the following lemma.

Assume that we choose uniformly at random a bit \(b\)  and we pass it through \(M\)  different BSC channels of crossover probability \(\frac{1-\varepsilon }{2}\)  and get as outputs \((y_1,\cdots ,y_M)\) . The BIMS channel corresponding to the output \((y_1,\cdots ,y_M)\)  is of capacity \(\Omega \left( M\varepsilon ^2 \right)\)  as long as \(M\varepsilon ^2 = \mathop {}\mathopen {}O\mathopen {}\left(1\right)\) .
We bring in the Bhattacharyya parameter \(Z\)  of a BIMS channel with transition probabilities \(p(y|b)\)  by
\(Z = \sum _y \sqrt{p(y|0)p(y|1)}.\) 
The Bhattacharyya parameter of a BSC channel of crossover probability \(\frac{1-\varepsilon }{2}\)  is
equal to \(Z(\varepsilon ) = 2\sqrt{\frac{1-\varepsilon }{2}\frac{1+\varepsilon }{2}} =\sqrt{1-\varepsilon ^2}\) .
By [6]} we know that the Bhattacharyya parameter \(Z\)  of our BIMS channel satisfies
\(Z = Z(\varepsilon )^M = (1- \varepsilon ^2)^{M/2}=1 - \Theta \left( M\varepsilon ^2 \right),\) 
as long as \(M\varepsilon ^2 = \mathop {}\mathopen {}O\mathopen {}\left(1\right)\) .
In the case of BIMS channel the capacity \(C\)  is lower-bounded by the Bhattacharyya parameter \(Z\)  as (see [7]}In this paper, this is actually a lower bound on the symmetric capacity, but capacity and symmetric capacity coincide for a BIMS channel.)
\(C \ge \log \frac{2}{1+Z}.\) 
This quantity is readily seen to be of order \(\Theta \left( M\varepsilon ^2 \right)\)  by using (REF ).
By putting all these ingredients together, we obtain a slightly more complicated algorithm taking into account multiple copies of LPN samples. The structure of the algorithm is the same, the only difference being how \(f_{{\mathbf {y}},{{H}}}\)  is defined. We now use (REF ) instead of (REF ).
This allows to obtain a slight generalization of Proposition REF  and remove the constraint (REF ) in it.

Assume that Create\(N\) ,\(w\) ,\({{P}}\)  produces \(N\)  parity-check equations in space \(\text{S}_{\text{eq}}\)  and time
\(\text{T}_{\text{eq}}\) . The probability \(\text{P}_{\text{succ}}\)  (over the choice of \({{N}}\) ) that there are exactly \(u\)  errors in \({{N}}\)  is given by
\(\text{P}_{\text{succ}}= \frac{\binom{s}{t-u}\binom{n-s}{u}}{\binom{n}{t}}.\)  The space complexity \(S\)  and the time complexity \(T\)  of the RLPN-decoder are given by
\(\textbf {Space:}\;\; S=\mathop {}\mathopen {}O\mathopen {}\left(\text{S}_{\text{eq}}+2^s\right), \quad \textbf {Time:}\;\; T = \mathop {}\mathopen {}\widetilde{O}\mathopen {}\left(\frac{\text{T}_{\text{eq}}+2^s}{\text{P}_{\text{succ}}}\right).\) 
The parameters \(s\) , \(u\)  and \(w\)  have to meet the constraint \(N \le \frac{\binom{n-s}{w}}{2^{k-s}}\) 
The algorithm outputs the correct \({\mathbf {e}}_{{P}}\)  with probability \(1-o(1)\)  if in addition we choose \(N\)  and
\(\text{N}_{\text{iter}}\)  such that
\(N &= &\omega \left(n \left(\frac{\binom{n-s}{w}}{K_w^{n-s}(u)}\right)^2 \right) \\\text{N}_{\text{iter}}& =& \omega \left(\frac{1}{\text{P}_{\text{succ}}}\right). \) 
If \(N \le 2^s\)  there is nothing to prove. However, if \(N\)  is bigger, say \(N = M2^s\)  with \(M >1\) , the length of the code we decode with the FFT is \(N^{\prime }=\Theta \left( 2^s \right)\)  and we use Lemma REF  and say that decoding this \([N^{\prime },s]\) -code is successful if \(N^{\prime } = \omega \left(\frac{n}{M\varepsilon ^2}\right)\) . By multiplying both terms by \(M\) , \(N =\omega \left(\frac{n}{\varepsilon ^2}\right)\) . We replace the bias \(\varepsilon \)  by its expression coming from Lemma REF  to finish the proof.

Collision techniques for finding low weight parity-checks
Using the [8]} method
A way for creating parity-checks with a low weight on \({{N}}\)  is simply to use subset-sum/collision techniques [8]}, [10]}, [11]}.
We start here with the simplest method for performing such a task pioneered by Dumer in [8]}.
Consider a parity-check matrix \({\mathbf {H}}\)  for the code \( we want to decode and keep only the columnsbelonging to \) N\( to obtain an \) (n-k)(n-s)\( matrix \) HN\(. The row-space of \) HN\( generates the restrictions \) hN\( to \) N\( of the parity-checks \) h\( of \) .
This row-space is nothing but the dual code \(\perp \)  punctured in \({{P}}\) , i.e. we keep only the positions in \({{N}}\) . With our notation, this is \(\perp _{{N}}\)  and is an \([n-s,n-k]\) -code. Therefore if we want to find parity-checks \({\mathbf {h}}\)  of \( such \) |hN|=w\(, this amounts to find codewords of \) N\( of weight \) w\(. For this, we compute a parity-check matrix \) H'\( of \) N\( {\em i.e. }a \) (k-s)(n-s)\( matrix such that\)\(\perp _{{N}}= \lbrace {\mathbf {c}}\in \mathbb {F}_2^{n-s}: {\mathbf {H}}^{\prime } {\mathbf {c}}^\intercal =0\rbrace .\)\(We split such a matrix in two parts\footnote {To simplify the presentation, the cut is explained by taking the first \frac{n-s}{2} positions for the first part and the \frac{n-s}{2} for the second part, but of course in general these positions are randomly chosen.} of the same size \) H'= H1  H2 \(. We obtain an algorithm of time and space complexity, \) T\( and \) S\( respectively, producing \) N\( codewords of weight \) w\(, with\begin{equation*}N = \frac{\binom{\frac{n-s}{2}}{\frac{w}{2}}^2}{2^{k-s}}(1+o(1)) \quad \mbox{and} \quad \mathrm {S}= \mathrm {T}= \mathop {}\mathopen {}O\mathopen {}\left(\binom{\frac{n-s}{2}}{\frac{w}{2}}+N\right).\end{equation*}The algorithm for producing such codewords is to set up two lists,\)\({{L}}_1\mathop {=}\limits ^{\triangle }\left\lbrace ({\mathbf {H}}_1 {\mathbf {h}}_1^\intercal ,{\mathbf {h}}_1): |{\mathbf {h}}_1|=\frac{w}{2},\; {\mathbf {h}}_1 \in \mathbb {F}_2^{\frac{n-s}{2}}\right\rbrace \)\(\)\({{L}}_2 \mathop {=}\limits ^{\triangle }\left\lbrace ({\mathbf {H}}_2 {\mathbf {h}}_2^\intercal ,{\mathbf {h}}_2): |{\mathbf {h}}_2|=\frac{w}{2}, \; {\mathbf {h}}_2 \in \mathbb {F}_2^{\frac{n-s}{2}}\right\rbrace \)\(and looking for collisions \) H1 h1=H2 h2\( in the lists. It yields vectors \) h'=h1 ||h2\( of weight \) w\( which are in \) N\( since \) H' h'=H1 h1+H2 h2=0\(. These vectors in \) F2n-s\( can be completed to give vectors \) hF2n\( such that \) hN=h'\(. The number of collisions is expected to be of order \) n-s2w22/2k-s\( since \) 2-(k-s)\( is the collision probability of two vectors in \) F2k-s\(.The algorithm for performing this task is given by Algorithm \ref {alg:collision}.\) [h!]
Creating low weight parity-checks by collisions
 Input \(, \) w\(, \) P\(\\\hspace*{0.0pt} \textbf {Output} a list of parity-check equations \) h\( of \)  such that \(|{\mathbf {h}}_{{N}}|=w\)  where                    \({{N}}\mathop {=}\limits ^{\triangle }\llbracket 1, n \rrbracket \setminus {{P}}\) .

Create\(,\) w\(, \) P\(\) 
\({\mathbf {H}}\leftarrow {Parity-check-matrix}{\perp ,{{P}}}\) 
returns a parity-check matrix for \(\perp \)  with an identity corresponding to the        positions in \({{P}}\)  :
\({\mathbf {H}}= \begin{pmatrix} {\mathbf {I}}&{\mathbf {P}}\\ \mathbf {0} & {\mathbf {H}}^{\prime } \end{pmatrix}\)  where we assume that the first block corresponds      to the positions of \({{P}}\) .
\({{L}}_1 \leftarrow \lbrace ({\mathbf {H}}_1 {\mathbf {h}}_1^\intercal ,{\mathbf {h}}_1): |{\mathbf {h}}_1|=w/2, {\mathbf {h}}_1 \in \mathbb {F}_2^{\frac{n-s}{2}}\rbrace \) 
\({{L}}_2 \leftarrow \lbrace ({\mathbf {H}}_2 {\mathbf {h}}_2^\intercal ,{\mathbf {h}}_2): |{\mathbf {h}}_2|=w/2, {\mathbf {h}}_2 \in \mathbb {F}_2^{\frac{n-s}{2}}\rbrace \) 
We assume \({\mathbf {H}}^{\prime }=\begin{pmatrix} {\mathbf {H}}_1 & {\mathbf {H}}_2 \end{pmatrix}\) , with \({\mathbf {H}}_1\)  and \({\mathbf {H}}_2\)  of the same size.
\({{L}}\leftarrow \lbrace {\mathbf {h}}_1 ||{\mathbf {h}}_2 \in {{L}}_1 \times {{L}}_2: {\mathbf {H}}_1{\mathbf {h}}_1^\intercal ={\mathbf {H}}_2{\mathbf {h}}_2^\intercal \rbrace \) 
\(\left\lbrace  {\mathbf {h}}^{\prime } {\mathbf {P}}^\intercal  ||{\mathbf {h}}^{\prime } : {\mathbf {h}}^{\prime } \in {{L}}\right\rbrace \) 
It is straightforward to check that \({\mathbf {h}}^{\prime } {\mathbf {P}}^\intercal  ||{\mathbf {h}}^{\prime }\)  belongs to \(\perp \) .
We have represented in Figure REF  the form of the parity-checks output by this method, together with the bet we make on the error.
<FIGURE>The amortized cost for producing a parity-check equation of weight \(w\)  is \(O(1)\)  as long as
\(N \ge \Omega \left( \binom{\frac{n-s}{2}}{\frac{w}{2}} \right)\) . It is insightful to consider the smallest value of \(w\)  for which
\(\binom{\frac{n-s}{2}}{\frac{w}{2}} \le {\binom{\frac{n-s}{2}}{\frac{w}{2}}^2}/{2^{k-s}}\) . This is roughly speaking
the smallest value (up to negligible terms) of \(w\)  for which the amortized cost for producing parity-check equations
of weight \(w\)  is \(O(1)\)  per equation. In such a case, we roughly have
\(N \approx \binom{\frac{n-s}{2}}{\frac{w}{2}} \approx \frac{\binom{\frac{n-s}{2}}{\frac{w}{2}}^2}{2^{k-s}} \approx 2^{k-s}.\) 
In other words with this choice we have
\(\text{T}_{\text{eq}}= \mathop {}\mathopen {}O\mathopen {}\left(2^{k-s}\right).\) 
Let us choose now \(u\)  as the “typical error weight” when restricted to \({{N}}\) , namely \(u \approx t \frac{n-s}{n}\)  and
\(s\)  such that the decoding complexity of the \([N,s]\)  code is also of order the codelength, i.e. \(N = \widetilde{\Theta }\left( 2^s \right)\) . This would imply \(2^s \approx 2^{k-s}\) , which means that we are going to choose \(s=\frac{k}{2}\) . By using Proposition REF , all these choices
would yield a time complexity \(\mathrm {T}_{\text{Dumer86}}\)  for decoding \( which would be of order\begin{equation}\mathrm {T}_{\text{Dumer86}} = \mathop {}\mathopen {}\widetilde{O}\mathopen {}\left(2^{k/2}\right),\end{equation}if the constraint \) N =  ( (n-swKwn-s(u))2 )\( for successful decoding the \) [N,s]\(-code is met.This amounts to\) 2Rn/2 =  ( (n(1-R/2)wKwn(1-R/2)(t(1-R/2)))2 )\(,where \) R\( is the code rate, {\em i.e. }\) R=kn\(. By using Proposition \ref {prop:bias}, we can give an asymptotic formula for this constraint. It translates into\)\(R/2 \ge 2(1-R/2) \widetilde{\varepsilon }\left(\tau ,\omega /(1-R/2)\right),\)\(where \)\( is the function defined in Proposition \ref {prop:bias}. Amazingly enough this constraint is met up to very small values of \) R\(, it is only below \) R 0.02\( that this condition is not met anymore. This innocent looking remark has actually very concrete consequences. This means that above the range \) R 0.02\( the asymptotic complexity exponent, {\em i.e. }\) Dumer86 =n 2 TDumer86 /n\( where\) TDumer86\( is the time complexity, satisfies\begin{equation}\alpha _{\text{Dumer86}} \le \frac{R}{2}.\end{equation}This is very surprising, since in the vicinity of \) R 0\( the asymptotic time complexity of {\em all known} decoding methods approach quickly \) R\(. In other words, in this regime, the complexity is of order \) T2Rn= 2k\( for full distance ({\em a.k.a} GV) decoding, meaning that they are not better thanexhaustive search. Unfortunately this is also the case for our method. It can namely be proved that even by optimizing on the value of \) s\(, \) w\( and \) u\( we can not do better than this with our method, since \) Dumer86(R) R\( as \) R\( approaches \) 0\(. However,as can be guessed from the fact that \) Dumer86 R2\( for \) R 0.02\(, the behavior of the complexity is much better for our RLPN decoder. This can be verified in Figure \ref {fig:RLPN-Dumer86vsPrange}. \\\)
It is worthwhile to recall that ISD algorithms in the regime of the rate close to 1 precisely use this collision method to find low weight codewords in order to reduce significantly the complexity of decoding.
In a sense, we have a dual version of the birthday/collision decoder of [8]} with reduced complexity for rates close to 0.
<FIGURE>
Improving [8]} by puncturing as in [11]}
There is a simple way of improving the generation of dual codewords of low weight on \({{N}}\) . It consists in partitioning \({{N}}\)  in two sets \({{N}}_1\)  and \({{N}}_2\)  with
\({{N}}_2\)  being a subset of positions of size just a little bit above \(n-k\)  (which is the dimension of the dual code \(\perp \) ), say \(n-k+\ell \)  and then to use the collision method to get dual codewords of weight \(w_2\)  on \({{N}}_2\) . The same method is used in the improvement [11]} of the simple collision decoder [8]} or in a slightly less efficient way in [10]}. 

It just consists in finding codewords in \(\perp \)  which have weight \(w_1\)  on \({{N}}_1\)  and \(w_2\)  on \({{N}}_2\)  instead of simply weight \(w\)  on \({{N}}\) . We have represented in Figure REF  the form of the parity-checks we produce with this method. Note that the weight \(w_1\)  is expected to be half the size \(k-\ell -s\)  of \({{N}}_1\) .
<FIGURE>We have however to be particularly careful here in filtering parity-checks with the right-weight \(w_1\)  on \({{N}}_1\) . Assume indeed that the weight of the error \({\mathbf {e}}\)  we try to recover is
\(u_1\)  on \({{N}}_1\) . If \(w_1 = \frac{k-\ell -s}{2}\)  and \(u_1\)  is odd, it turns out that the bias of such parity-checks is 0 (this is a consequence of Lemma REF  below).
To understand the bias we get in this case, the proof of Proposition REF  can be readily adapted to yield

Assume that the code \( is chosen by picking for it an \) (n-k) n\( binary parity-check matrix uniformly at random.Let \) N\( be a fixed set of \) n-s\( positions in \) 1, n \( which is partitioned in two sets \) N1\( and \) N2\( and \) e\( be some error of weight \) ui\( on \) Ni\( for \) i {1,2}\(. For \) i {1,2}\(, choose \) h\( uniformly at random among the parity-checks of \)  of weight \(w_i\)  on the \({{N}}_i\) 's and \({\mathbf {h}}^{\prime }\)  uniformly at random among the words of weight \(w_i\)  on the \({{N}}_i\) 's. For \(i \in \lbrace 1,2\rbrace \) , let
\(\delta _i & \mathop {=}\limits ^{\triangle }& \operatornamewithlimits{bias}\left( \left\langle {\mathbf {e}}_{{{N}}_i} , {\mathbf {h}}^{\prime }_{{{N}}_i} \right\rangle  \right)\\\delta & \mathop {=}\limits ^{\triangle }& \delta _1 \delta _2\) 
If the parameters \(k\) , \(s\) , \(u_i\) , \(w_i\)  are chosen as functions on \(n\)  so that for \(n\)  going to infinity, the expected number \(N\)  of parity-checks of \( of respective weight \) wi\( on \) Ni\( for \) i {1,2}\(, satisfies\) N = ( 1 / 2 )\( then for all but a proportion \) o(1)\( of codes we have\)\(\operatornamewithlimits{bias}\left( \langle \mathbf {e}, \mathbf {h}\rangle \right) = (1+o(1)) \delta .\)\(\)
With the collision method we use, the parity-checks we produce have actually a slightly more specific form, since \({{N}}_2\)  is partitioned in two sets of (almost) the same size on which \({\mathbf {h}}\)  has weight \(w_2/2\) . It is not difficult to turn such a generation of parity-checks at the cost of a polynomial overhead into a generation of uniformly distributed parity-checks of weight \(w_2\)  on \({{N}}_2\) . We leave out the details for doing this here. Under such an assumption, we have

With the same assumptions as in Proposition REF ,
\(\mathbb {P}_{\mathbf {h}}(\langle \mathbf {e}_{{{N}}}, \mathbf {h}_{{{N}}}=1\rangle ) = \frac{1 - \varepsilon }{2} \quad \mbox{where} \quad \varepsilon = \delta _1 \cdot \delta _2 (1-o(1))\) 
with \(\delta _1 \mathop {=}\limits ^{\triangle }\frac{ K_{w_1}^{k-\ell -s}(u_1)}{\binom{k-\ell -s}{w_1}}\) , \(\delta _2 \mathop {=}\limits ^{\triangle }\frac{ K_{w_2}^{n-k+\ell }(u_2)}{\binom{n-k+\ell }{w_2}}\) , \(u_1 \mathop {=}\limits ^{\triangle }|{\mathbf {e}}_{{{N}}_1}|\) , \(u_2 \mathop {=}\limits ^{\triangle }|{\mathbf {e}}_{{{N}}_2}|\) , \(w_1 \mathop {=}\limits ^{\triangle }|\mathbf {h}_{{{N}}_1}|\)
and \(w_2 \mathop {=}\limits ^{\triangle }|\mathbf {h}_{{{N}}_2}|\) .
This is a straightforward application of the previous proposition and
Lemma REF .
All these considerations lead to a slight variation of the RLPN decoder given in Algorithm REF . Let us make now a bet on the weight
\(u_i\)  of the error restricted to \({{N}}_i\)  for \(i \in \lbrace 1,2\rbrace \)  and use Dumer's [11]} collision low-weight codeword generator to produce \(N\)  parity-checks \({\mathbf {h}}\)  such that \(\left|{\mathbf {h}}_{{{N}}_i}\right|=w_i\)  for \(i \in \lbrace 1,2\rbrace \) . We call the associated function Create\(N\) ,\(w_1\) ,\(w_2\) , \({{P}}\) .
We assume that Create\(N\) ,\(w_1\) ,\(w_2\) , \({{P}}\)  produces \(N\)  parity-check equations in space \(\text{S}_{\text{eq}}\)  and time
\(\text{T}_{\text{eq}}\)  that are of weight \(w_i\)  on \({{N}}_i\)  for \(i \in \lbrace 1,2\rbrace \) . The probability \(\text{P}_{\text{succ}}\)  (over the choice of \({{N}}_1\)  and \({{N}}_2\) ) that there are exactly \(u_1\)  errors in \({{N}}_1\)  and \(u_2\)  errors in \({{N}}_2\)  is given by
\(\text{P}_{\text{succ}}= \frac{\binom{s}{t-u_1-u_2}\binom{k-\ell -s}{u_1}\binom{n-k+\ell }{u_2}}{\binom{n}{t}}.\) 
The space complexity \(\mathrm {S}_{\text{Dumer89}}\)  and time complexity \(\mathrm {T}_{\text{Dumer89}}\)  of the RLPN-decoder are given by
\(\textbf {\textup {Space:}}\;\; S=\mathop {}\mathopen {}O\mathopen {}\left(\text{S}_{\text{eq}}+2^s\right), \quad \textbf {\textup {Time:}}\;\; T = \mathop {}\mathopen {}\widetilde{O}\mathopen {}\left(\frac{\text{T}_{\text{eq}}+2^s}{\text{P}_{\text{succ}}}\right).\) 
under the constraint on the parameters \(s\) , \(u_1\) , \(u_2\) , \(w_1\)  and \(w_2\)  given by
\(N = \widetilde{\Omega } \left( \left(\frac{\binom{k-\ell -s}{w_1}\binom{n-k+\ell }{w_2}}{K_{w_1}^{k-\ell -s}(u_1)K_{w_2}^{k-\ell -s}(u_2)}\right)^2 \right).\) 

From this proposition we readily obtain the following asymptotic form

The asymptotic complexity exponent of the RLPN decoder based on Dumer's collision low weight dual codeword generators is given by
\(\alpha _{\text{Dumer89}}(R) \mathop {=}\limits ^{\triangle }\min _{(\sigma ,\nu _1,\nu _2,\lambda ,\omega _1,\omega _2) \in {{R}}} \beta (R,\sigma ,\nu _1,\nu _2,\lambda ,\omega _1,\omega _2)\) 
where
\(\beta (R,\sigma ,\nu _1,\nu _2,\lambda ,\omega _1,\omega _2) \mathop {=}\limits ^{\triangle }\max \left( \sigma ,\nu (R,\lambda ,\omega _2) \right)+ \pi (R,\sigma ,\nu _1,\nu _2,\lambda ),\) 
\(\nu (R,\lambda ,\omega _2) \mathop {=}\limits ^{\triangle }\max { \left( \frac{(1-R+\lambda )}{2} h\left( \frac{\omega _2}{1-R+\lambda }\right) , (1-R+\lambda ) h\left( \frac{\omega _2}{1-R+\lambda }\right) -\lambda \right)},\) 
\(\pi (R,\sigma ,\nu _1,\nu _2,\lambda ) \mathop {=}\limits ^{\triangle }1-R -\sigma h\left( \frac{\tau -\nu _1-\nu _2}{\sigma }\right)-(R-\lambda -\sigma ) h\left( \frac{\nu _1}{R-\lambda -\sigma } \right) -(1-R+\lambda ) h \left( \frac{\nu _2}{1-R+\lambda }\right),\) 
\(\tau \mathop {=}\limits ^{\triangle }\delta _{\mathrm {GV}}(R) = h^{-1}(1-R)\) 
and the constraint region \({{R}}\)  is defined by the subregion of nonnegative tuples \((\sigma ,\nu _1,\nu _2,\lambda ,\omega _1,\omega _2)\)  such that
\(\sigma \le R - \lambda , \quad \nu _1 \le R- \lambda - \sigma , \quad \nu _2 \le 1- R + \lambda , \quad \tau - \sigma \le \nu _1+\nu _2 \le \tau , \quad \omega _1 = \frac{R - \lambda - \sigma }{2}\) 
and
\(\nu (R,\lambda ,\omega _2) = - (R-\lambda -\sigma )\widetilde{\varepsilon }(\frac{\nu _1}{R-\lambda -\sigma },\frac{\omega _1}{R-\lambda -\sigma }) - (1-R+\lambda )\widetilde{\varepsilon }(\frac{\nu _2}{1-R+\lambda },\frac{\omega _2}{1-R+\lambda })\) 
where \(\widetilde{\varepsilon }\)  is the function defined in Proposition REF .

Using advanced collision techniques
ISD techniques have evolved [10]}, [11]}, [22]}, [23]}, [24]} by first introducing [10]} collision/subset-sum techniques
whose purpose is to produce for codes of rate close to 1, all codewords of some small weight, and later on by substantially improving them by using on top of that for instance representation techniques [23]}. These algorithms come very handy in our case for devising the function Create\(N,w,{{P}}\)  that we need. In the previous section, we have explored what could be achieved by the very first techniques of this type taken from [8]}, [11]}. We are
going to explain now what can be gained by using [23]}, [24]}.
It is convenient here to formalize the basic step used in the previous section which can be explained by the following function

 Input: \({{L}}_1 \subseteq \mathbb {F}_2^n\) , \({{L}}_2\subseteq \mathbb {F}_2^n\) , \(w \in \llbracket 1, n \rrbracket \) , \({\mathbf {H}}\in \mathbb {F}_2^{\ell \times n}\)
 Output: a list \({{L}}= \lbrace {\mathbf {x}}={\mathbf {x}}_1+{\mathbf {x}}_2: {\mathbf {x}}_i \in {{L}}_i,\;i\in \lbrace 1,2\rbrace ,\;|{\mathbf {x}}|=w,\;{\mathbf {H}}{\mathbf {x}}^\intercal  = \mathbf {0} \rbrace \)  of elements
of the form \({\mathbf {x}}_1+{\mathbf {x}}_2\)  with \({\mathbf {x}}_i\)  belonging to \({{L}}_i\)  of weight \(w\)  belonging to the code of parity-check matrix \({\mathbf {H}}\) 

Merge\({{L}}_1,{{L}}_2,w,{\mathbf {H}}\) 
\({{L}}\leftarrow \emptyset \) 
\({\mathbf {x}}_1 \in {{L}}_1\) 
Store \({\mathbf {x}}_1\)  in a hashtable \({{T}}\)  at address \({\mathbf {H}}{\mathbf {x}}_1^\intercal \) 
\({\mathbf {x}}_2 \in {{L}}_2\) 
\(\exists {\mathbf {x}}_1\)  in \({{T}}\)  at address \({\mathbf {H}}{\mathbf {x}}_2^\intercal \)  and \(|{\mathbf {x}}_1+{\mathbf {x}}_2|=w\) 
Put \({\mathbf {x}}_1+{\mathbf {x}}_2\)  in \({{L}}\) 
\({{L}}\)
It creates codewords of weight \(w\)  in a code of parity-check matrix \({\mathbf {H}}\)  as sums \({\mathbf {x}}_1 + {\mathbf {x}}_2\)  of two lists \({{L}}_1\)  and \({{L}}_2\)  with a complexity which is of the form
\(\mathop {}\mathopen {}O\mathopen {}\left(\max \left(\#{{L}}_1,\#{{L}}_2,\frac{\#{{L}}_1\cdot \#{{L}}_2}{2^\ell } \right)\right)\)  if the \({\mathbf {H}}{\mathbf {x}}_i^\intercal \) 's are independently distributed uniformly at randomise (we will make this assumption from now on). It is clear that [8]} and [11]} is more or less a direct application of this method. [23]} and [24]} use several layers of this function.
[23]} starts by partitioning the set of positions of the vectors of \(\mathbb {F}_2^n\)  which are considered in two sets \({{I}}_1\)  and \({{I}}_2\)  of about the same size. Then it starts with two lists \({{L}}_1^0\)  and \({{L}}^0_2\)  of all elements of weight \(p_0\)  and support \({{I}}_1\)  and \({{I}}_2\)  respectively. It merges them in a list \({{L}}^1\)  of elements of weight \(p_1\)  in the kernel of a parity-check matrix \({\mathbf {H}}_1\) . Since the elements of \({{L}}_1^0\)  and \({{L}}^0_2\)  have disjoint supports by construction, we necessarily have that \(p_1=2p_0\) . \({{L}}^1\)  is then merged with itself to yield elements which are in the kernel of another matrix \({\mathbf {H}}_2\)  (see Figure REF ). Since these are sums of elements of \({{L}}^1\)  they are also in the kernel of \({\mathbf {H}}_1\) , so that that the elements of the final list are of weight \(p_2\)  and belong to the code of parity-check
\({\mathbf {H}}= \begin{pmatrix} {\mathbf {H}}_1 \\ {\mathbf {H}}_2 \end{pmatrix}\) . The size of \({\mathbf {H}}_1\)  is chosen such that an element \({\mathbf {x}}\)  of weight \(p_2\)  and \({\mathbf {H}}_1 {\mathbf {x}}^\intercal =0\)  is typically the sum of only two elements of \({{L}}^1\)  (this is the point of the representation technique). [24]} is similar to [23]} with one layer which is added. In this case, we create at the end a list of elements of weight \(p_3\)  which are in the code of parity-check matrix
\({\mathbf {H}}\mathop {=}\limits ^{\triangle }\begin{pmatrix} {\mathbf {H}}_1 \\ {\mathbf {H}}_2 \\ {\mathbf {H}}_3 \end{pmatrix}\) 
(see Figure REF ). The sizes of \({\mathbf {H}}_1\)  in the [23]} case, and of \({\mathbf {H}}_1\)  and \({\mathbf {H}}_2\)  in [24]} are chosen to ensure unicity of the representation of an element of a list as the sum of two elements of the lists used for the merge (this is the representation technique).
<FIGURE>We use these two techniques as we used the [8]} technique inside the [11]} technique, namely to generate codewords of \(\perp \)  (i.e. \({\mathbf {H}}{\mathbf {x}}^\intercal =\mathbf {0}\)  for \({\mathbf {H}}\)  given by (REF )) which are of weight \(p_{3}\)  on a set of indices of size \(n-k+\ell \)  (see Figure REF ).
<FIGURE>If we let \(\ell _1\)  be the number of rows of \({\mathbf {H}}_1\) , \(\ell _2\)  be the number of rows of the matrix of \({\mathbf {H}}_2^{\prime } \mathop {=}\limits ^{\triangle }\begin{pmatrix} {\mathbf {H}}_1 \\ {\mathbf {H}}_2 \end{pmatrix}\) , then the fact that the elements of \({{L}}^2\)  should have a unique representation in terms of a sum of a pair of elements of \({{L}}^1\)  respectively and that they are all elements \({\mathbf {x}}\)  of weight \(p_1\)  and \(p_2\)  respectively which satisfy \({\mathbf {H}}_2^{\prime } {\mathbf {x}}^\intercal =\mathbf {0}\)  and \({\mathbf {H}}{\mathbf {x}}^\intercal =\mathbf {0}\)  respectively, imposes conditions (REF ) which follow.
The \(S_i\)  represent the space complexity of the successive lists (i.e. \({{L}}^0\) , \({{L}}^1\) , \({{L}}^2\)  and \({{L}}^3\) ) used in the [24]} algorithm, whereas the \(T_i\) 's denote the complexity of each merge and \(\text{T}_{\text{eq}}\)  is the final complexity.
\(2^{\ell _1} &= \binom{p_2}{p_2/2}\binom{n-k+\ell -p_2}{p_1-p_2/2},& 2^{\ell _2} &= \binom{p_3}{p_3/2}\binom{n-k+\ell -p_3}{p_2-p_3/2} \) 
\(S_0 = \binom{\frac{n-k+\ell }{2}}{\frac{p_1}{2}}, \quad S_1 = \frac{\binom{n-k+\ell }{p_1}}{2^{\ell _1}}, \quad S_2 = \frac{\binom{n-k+\ell }{p_2}}{2^{\ell _2}}, \quad S_3 = \frac{\binom{n-k+\ell }{p_3}}{2^{\ell }}\) 
\(T_0 = S_0, \quad T_1 = S_0 + \frac{S_0^2}{2^{\ell _1}}, \quad T_2 = S_1 + \frac{S_1^2}{2^{\ell _2-\ell _1}}, \quad T_3 = S_2 + \frac{S_2^2}{2^{\ell -\ell _2}},\quad \text{T}_{\text{eq}}= T_0+T_1+T_2+T_3\) 
There is a similar proposition as Proposition REF  which gives the asymptotic complexity of the RLPN decoder used in conjunction with the [23]} or [24]} techniques for producing low weight codewords. For [23]} it is given by

propositionMMT
The asymptotic complexity exponent of the RLPN decoder based on [23]} is given by
\(\alpha _{\text{MMT}}(R) \mathop {=}\limits ^{\triangle }\min _{(\sigma ,\nu _1,\nu _2,\lambda ,\lambda _1,\omega _1,\omega _2,\pi _1) \in {{R}}} \beta (R,\sigma ,\nu _1,\nu _2,\lambda ,\lambda _1,\omega _1,\omega _2,\pi _1)\) 
where
\(\beta & \mathop {=}\limits ^{\triangle }& \max (\sigma ,\nu ) + \pi , \\\nu & \mathop {=}\limits ^{\triangle }& \max (\gamma _1,\gamma _2),\\\gamma _1 & \mathop {=}\limits ^{\triangle }& \max \left(\frac{1-R+\lambda }{2}h\left(\frac{\pi _1}{1-R+\lambda } \right),(1-R+\lambda )h\left(\frac{\pi _1}{1-R+\lambda } \right)-\lambda _1\right),\\\gamma _2 & \mathop {=}\limits ^{\triangle }& 2(1-R+\lambda )h\left(\frac{\pi _1}{1-R+\lambda } \right)-\lambda _1-\lambda ,\\\rho & \mathop {=}\limits ^{\triangle }& 1-R -\sigma h\left( \frac{\tau -\nu _1-\nu _2}{\sigma }\right) -(R-\lambda -\sigma ) h\left( \frac{\nu _1}{R-\lambda -\sigma } \right) -(1-R+\lambda ) h \left( \frac{\nu _2}{1-R+\lambda }\right),\\\tau & \mathop {=}\limits ^{\triangle }& \delta _{\mathrm {GV}}(R) = h^{-1}(1-R)\) 
and the constraint region \({{R}}\)  is defined by the subregion of nonnegative tuples \((\sigma ,\nu _1,\nu _2,\lambda ,\lambda _1,\pi ,\omega _1,\omega _2)\)  such that
\(\sigma \le R-\lambda , \quad \lambda _1 \le \lambda , \quad \pi _1 \le \omega _2, \quad \nu _1 \le R- \lambda - \sigma , \quad \nu _2 \le 1- R + \lambda , \quad \tau - \sigma \le \nu _1+\nu _2 \le \tau ,\) 
\(\omega _1 = \frac{R - \lambda - \sigma }{2}, \quad \omega _2 < 1-R+\lambda ,\) 
\(\frac{\omega _2 }{2}< \pi _1 < 1-R+\lambda , \quad \lambda _1 = \omega _2 + (1-R+\lambda - \omega _2)h\left( \frac{\pi _1-\omega _2/2}{1- R+\lambda -\omega _2}\right) ,\) 
\((1-R+\lambda )h\!\left(\!\!\frac{\omega _2}{1-R+\lambda }\!\!\right)\!-\!\lambda = -\!(R-\lambda -\sigma )\tilde{\varepsilon }(\frac{\nu _1}{R-\lambda -\sigma },\frac{\omega _1}{R-\lambda -\sigma })\\-(1-R+\lambda )\tilde{\varepsilon }(\frac{\nu _2}{1-R+\lambda },\frac{\omega _2}{1-R+\lambda }),\) 
where \(\widetilde{\varepsilon }\)  is the function defined in Proposition REF .
We give a proof in the Appendix  for reference. There is a similar proposition for the asymptotic behavior of RLPN decoding used together with [24]} which is given in the Appendix . We have used them for producing the complexity curves given in Figure REF  which display the various complexities of the RLPN decoders we have presented. Even if there is a tiny improvement by using [24]} instead of [23]} the two curves are nearly indistinguishable. A perspective of improvement of our algorithm could be to produce the parity-check equations by using more recent ISD techniques than [24]}, in particular [51]} or [52]} which both use nearest-neighbor search. Our preliminary results using in particular [51]} do not provide significant improvement, we have only been able to achieve a very slightly better complexity for rates close to \(0.2\) .

A Lower bound on the complexity of RLPN decoders
As pointed out all along the paper, RLPN decoding needs a large number \(N\)  of parity-check equations to work but of some shape as indicated below



t (-0.5,0.25) \(\mathbf {h}\) ;
(0,0) rectangle (12,0.5);
[pattern = north east lines] (0,0) rectangle (2.5,0.5);
[<->, >=stealth] (0.025,0.75) – (2.45,0.75);
t (1.25,1) \(s\) ;
(2.5,0) rectangle (12,0.5);
[<->, >=stealth] ((2.525,0.75) – (11.95,0.75);
t (7.25,1) \(n-s\) ;
t (7.25,0.25) \(w\) ;


where the hatched area indicates that the weight is arbitrary on this part while \(\mathbf {h}\)  restricted on the other positions needs to have Hamming weight \(w\) . The number \(N\)  of such parity-checks has to verify (see Proposition REF )
\(N = \widetilde{\Omega } \left( \left(\frac{\binom{n-s}{w}}{K_w^{n-s}(u)}\right)^2 \right)\) 
in order to be able to solve the underlying LPN problem. It can be verified that the smaller \(w\)  is (the bigger is the bias \(\varepsilon \) ), the smaller is \(N\)  and the more efficient is our algorithm. Obviously if \(w\)  is too small, there are not enough such parity-checks.
It can be verified that the expected number of parity-checks of the aforementioned shape is given by \(2^{s} \binom{n-s}{w}/2^{k}\)  in a random code (which is our assumption). Therefore we need
\(N =\mathop {}\mathopen {}O\mathopen {}\left( \frac{2^{s} \binom{n-s}{w}}{2^{k}}\right).\) 
Given this picture it is readily seen that the complexity of RLPN decoding is always lower-bounded by \(N\)  (which is at least the cost to produce \(N\)  parity-checks) but we can be more accurate on the lower-bound over the complexity. Recall that we first need to solve an underlying LPN problem and that we make a bet on the number of errors \(u\)  in \({{N}}\) . Therefore, assuming that we can compute a parity-check of the aforementioned shape in time \(O(1)\) , the complexity of our extended statistical decoding is given by
\(\widetilde{O}\left( \frac{1}{\text{P}_{\text{succ}}} \;\max \left( 2^{s}, N \right) \right)\) 
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 [54]} 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>
Concluding remarks
Since Prange's seminal work [55]} 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 [8]} 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 [10]}, [11]} 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 [52]}. 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.

Acknowdgement
The work of TDA was funded by the French Agence Nationale de la Recherche through ANR JCJC COLA (ANR-21-CE39-0011). We wish also to thank Ilya Dumer for his very insightful thoughts about decoding linear codes in the low rate regime.


Appendices


Asymptotic complexity of the RLPN decoder used in conjunction with the [23]} and [24]} technique
[Proof of Proposition ]
In the case of the MMT technique we have the following set of equalities
\(2^{\ell _1} = \binom{w_2}{w_2/2}\binom{n-k+\ell -w_2}{p_1-w_2/2}\) 
\(S_0 = \binom{\frac{n-k+\ell }{2}}{\frac{p}{2}}, \;\;\;S_1 = \frac{\binom{n-k+\ell }{p}}{2^{\ell _1}}, \;\;\;S_2 = \frac{\binom{n-k+\ell }{w_2}}{2^{\ell }}\) 
\(T_0 = S_0, \quad T_1 = S_0 + \frac{S_0^2}{2^{\ell _1}}, \quad T_2 = S_1 + \frac{S_1^2}{2^{\ell -\ell _1}}, \quad \text{T}_{\text{eq}}= T_0+T_1+T_2\) 
We let
\(\sigma \mathop {=}\limits ^{\triangle }\frac{s}{n}, \quad \lambda \mathop {=}\limits ^{\triangle }\frac{\ell }{n}, \quad \lambda _1 \mathop {=}\limits ^{\triangle }\frac{\ell _1}{n}, \quad \pi \mathop {=}\limits ^{\triangle }\frac{p}{n}, \quad \omega _2 \mathop {=}\limits ^{\triangle }\frac{w_2}{n}, \quad \nu _1 \mathop {=}\limits ^{\triangle }\frac{v_1}{n}, \quad \nu _2 \mathop {=}\limits ^{\triangle }\frac{v_2}{n}.\) 
The equality
\(2^{\ell _1} = \binom{w_2}{w_2/2}\binom{n-k+\ell -w_2}{p_1-w_2/2}\) 
translates into
\(\lambda _1 = \omega _2 + (1-R+\lambda - \omega _2)h\left( \frac{\pi -\omega _2/2}{1-R+\lambda -\omega _2}\right).\) 
In our case, the number \(N\)  of parity-check which are produced is equal to \(S_2\)  and therefore the condition
\(N = \widetilde{\Omega } \left( \left(\frac{\binom{k-\ell -s}{w_1}\binom{n-k+\ell }{w_2}}{K_{w_1}^{k-\ell -s}(u_1)}\right)^2 \right).\) 
of Proposition REF  becomes
\((1-R+\lambda )h\!\left(\!\!\frac{\omega _2}{1-R+\lambda }\!\!\right)-\lambda = -\!(R-\lambda -\sigma )\tilde{\varepsilon }(\frac{\nu _1}{R-\lambda -\sigma },\frac{\omega _1}{R-\lambda -\sigma }) \\-(1-R+\lambda )\tilde{\varepsilon }(\frac{\nu _2}{1-R+\lambda },\frac{\omega _2}{1-R+\lambda }).\) 
The asymptotic complexity exponent of the RLPN decoder based on [24]} is given by
\(\alpha _{\text{BJMM}}(R) = \min _{(\sigma ,\nu _1,\nu _2,\lambda ,\lambda _1,\lambda _2,\pi _1,\pi _2,\omega _1,\omega _2) \in {{R}}} \beta (\sigma ,\nu _1,\nu _2,\lambda ,\lambda _1,\lambda _2,\pi _1,\pi _2,\omega _1,\omega _2)\) 
where
\(\beta & \mathop {=}\limits ^{\triangle }& \min ( \sigma ,\nu + \rho ) \;\;\text{with} \\\nu &= & \max (\gamma _1,\gamma _2,\gamma _3)\; \;\\\gamma _1 & = & \max \left(\frac{1-R+\lambda }{2}h\left(\frac{\pi _1}{1-R+\lambda } \right),(1-R+\lambda )h\left(\frac{\pi _1}{1-R+\lambda } \right)-\lambda _1\right)\\\gamma _2 & = & 2(1-R+\lambda )h\left(\frac{\pi _1}{1-R+\lambda } \right)-\lambda _1-\lambda _2\\\gamma _3 & = & 2(1-R+\lambda )h\left(\frac{\pi _2}{1-R+\lambda } \right)-\lambda - \lambda _2\\\rho &= & 1-R -\sigma h\left( \frac{\tau -\nu _1-\nu _2}{\sigma }\right)-(R-\lambda -\sigma ) h\left( \frac{\nu _1}{R-\lambda -\sigma } \right) -(1-R+\lambda ) h \left( \frac{\nu _2}{1-R+\lambda }\right)\\\tau & \mathop {=}\limits ^{\triangle }& \delta _{\mathrm {GV}}(R) = h^{-1}(1-R)\) 
and the constraint region \({{R}}\)  is defined by the sub-region of nonnegative tuples \((\sigma ,\nu _1,\nu _2,\lambda ,\lambda _1,\lambda _2,\pi _1,\pi _2,\omega _1,\omega _2)\)  such that
\(\sigma \le R-\lambda , \quad \lambda _1 \le \lambda _2 \le \lambda , \pi _1 \le \pi _2 \le \omega _2, \quad \nu _1 \le R- \lambda - \sigma , \quad \nu _2 \le 1- R + \lambda , \quad \tau - \sigma \le \nu _1+\nu _2 \le \tau ,\) 
\(\pi _1 \ge \frac{\pi _2}{2}, \quad \pi _2 \ge \frac{\omega _2}{2}, \quad \pi _2 < \lambda _1, \quad \omega _2 < \lambda _2, \quad \pi _1 < 1-R + \lambda , \quad \omega _1 = \frac{R - \lambda - \sigma }{2} ,\) 
\(\lambda _1 & = & \pi _2 + (1-R+\lambda - \pi _2)h\left( \frac{\pi _1-\pi _2/2}{1- R+\lambda -\pi _2}\right),\\\lambda _2 & = & \omega _2 + (1-R+\lambda - \omega _2)h\left( \frac{\pi _2-\omega _2/2}{1- R+\lambda -\omega _2}\right)\) 
and
\((1-R+\lambda )h\!\left(\!\!\frac{\omega _2}{1-R+\lambda }\!\!\right)\!-\!\lambda = -\!(R-\lambda -\sigma )\tilde{\varepsilon }(\frac{\nu _1}{R-\lambda -\sigma },\frac{\omega _1}{R-\lambda -\sigma }) \\-(1-R+\lambda )\tilde{\varepsilon }(\frac{\nu _2}{1-R+\lambda },\frac{\omega _2}{1-R+\lambda })\) 
where \(\widetilde{\varepsilon }\)  is the function defined in Proposition REF .

About [63]}
We have compared all along the paper our results to the state-of-the-art for solving the decoding problem. To date, the best complexity is achieved in [52]} which essentially uses the techniques in [51]} with an additional stage.
There is another result in the literature which claims better results than [52]}. Indeed, in [63]}, the same authors pretend that we can get a gain of \(\approx \)  7% for full decoding and at the worst code rate in comparison with [52]}. However, this result is flawed: there is indeed an error in the analysis of this new decoding algorithm which leads to this result. The decoding algorithm in [63]} essentially consists in producing lists recursively by using nearest-neighbor searches at each stage; the solution of the decoding problem is then contained in the last list. Thus, an accurate analysis of this algorithm lies in the good estimation of the size of the various lists. In [63]}, an upper bound of the size of these lists is given. Unfortunately this upper bound does not hold.
Let us recall it. It is a bound of the list-size \(S_i\)  at stage \(i\) :
\(\begin{array}{lcl}S_i & \le & \left|\lbrace \ \mathbf {x} \in \mathbb {F}^k_2, |\mathbf {x}| = p_i\rbrace \right| \cdot \underset{\mathbf {x} \in \mathbb {F}^{\ell _i}_2}{\mathbb {P}} \left(|\mathbf {x}| = \omega _i^{(i)}\right) \\& & \ \ \ \cdot \displaystyle {\prod _{h=1}^{i-1}} \underset{\mathbf {x},\mathbf {y} \in \mathbb {F}^{\ell _h}_2}{\mathbb {P}} \left(|\mathbf {x}+\mathbf {y}| = \omega _h^{(i)} \ : \ |\mathbf {x}| = |\mathbf {y}| = \omega _h^{(i-1)}\right)\end{array}\) 
We use here the notation from [63]}: at each stage \(i \in \lbrace 1..m\rbrace \) , the algorithm is producing lists of \(S_i\)  vectors with weight \(p_i\)  on an information set and weight \(\left(\omega _h^{(i)} \right)_{h \in \lbrace 1..i\rbrace }\)  on redundancy subsets of respective length \(\left(\ell _i \right)_{h \in \lbrace 1..i\rbrace }\) . Since the list at the final stage \(m\)  contains the solution, the decoding distance \(\omega \)  that we aim to achieve is \(\omega = p_3 + \sum _{i = 1}^{m} \omega _i\) .
We have noticed that there is a problem with (REF ) by running simulations. For instance, let look at the following parameters for depth \(m = 3\) :

<TABLE>
The Equation (REF ) tells us that \(S_2\)  should not be bigger than \(13.66\)  whereas in practice it is \(33.12\) . The problem lies in the fact that in (REF ), the probability
\(\mathbf {P} \mathop {=}\limits ^{\triangle }\mathbb {P} \left( |\mathbf {y}_i| = \omega _i^{(i)}\right) \cdot \prod _{h=1}^{i-1} \mathbb {P}\left(|\mathbf {y}^{\prime }_{h}+\mathbf {y}^{\prime \prime }_{h}| = \omega _h^{(i)} \right)\) 
represents the probability that a pair from the lists at stage \(i-1\)  produces an element in the list at stage \(i\) , but it is not the probability that a vector of length \(k\)  and weight \(p_i\)  is in that list as it is suggested by Equation (REF ). If we do not filter the duplicates, the actual expected size of the lists at stage \(i\)  is \(N^{\prime } \mathbf {P}\)  where
\(N^{\prime } \mathop {=}\limits ^{\triangle }L_{i-1}^2 \cdot \frac{\binom{k - p_{i-1}}{p_i/2}\binom{p_{i-1}}{p_i/2}}{\binom{k}{p_{i-1}}}\) 
is the number of pairs in a list at stage \(i-1\)  which are a representation of a vector of weight \(p_i\) . After filtering the duplicates in the resulting lists, we finally obtain
\(S_i = \mathcal {O}\left({\min \left( N^{\prime } \mathbf {P}\ , \ L_i \right)} \right)\) 
where \(L_i\)  is the maximal size of the list, obtained when the whole set of vectors with the desired weight distribution is typically produced by the algorithm at the considered stage; thus we have
\(L_i = \binom{k}{p_i} \prod _{h=1}^{i} \frac{\binom{\ell _h}{w_h^{(i)}} }{2^{\ell _h}}\) 
Note that if the assumptions in the correctness lemma [63]} are met, then we actually have \(L_{i} = S_i\) .
This phenomenon can notably be observed for the input values of parameters given in the paper.
For instance, in [63]} the following parameters are given for the full decoding at the hardest rate \(\frac{k}{n} = 0.46\) :

\(& & \frac{\ell _1}{n} & = 0.0366 & \frac{\ell _2}{n} & = 0.0547 & \frac{\ell _3}{n} &= 0.0911 & \frac{\ell _4}{n} &= 0.3576 \\\frac{p_1}{n} &= 0.00559 & \frac{w_1^{(1)}}{n} &= 0.011515 & & & & & & \\\frac{p_2}{n} &= 0.01073 & \frac{w_1^{(2)}}{n} &=0.023029 & \frac{w_2^{(2)}}{n} &= 0.016676 & & & & \\\frac{p_3}{n} &= 0.02029 & \frac{w_1^{(3)}}{n} &= 0.0232 & \frac{w_2^{(3)}}{n} &=0.033351 & \frac{w_3^{(3)}}{n} &= 0.009993 & & \\\frac{p_4}{n} &= 0.03460& \frac{w_1^{(4)}}{n} &= 0.0066 & \frac{w_2^{(4)}}{n} &= 0.0099 & \frac{w_3^{(4)}}{n} &= 0.0114 & w_4^{(4)}&=0.0612\) 


With these parameters, if we believe the bound (REF ), we should have
\(S_0 \le 2^{0.02179 n} & & S_1 \le 2^{0.03987 n} & & S_2 \le 2^{0.05939 n} & & S_3 \le 2^{0.05975 n}\) 

But since the correctness lemma is verified we can use formula (REF ) to compute the expected size of the lists:
\(S_0 = 2^{0.02179 n} & & S_1 = 2^{0.03987 n} & &S_2 = 2^{0.0655 n} & & S_3= 2^{0.0705 n}\) 

We can see that \(S_2\)  and \(S_3\)  exceed their presumed upper bound, which increases the complexity of the algorithm to \(C = \mathcal {O}\left(2^{0.1083 n}\right)\)  in comparison to the claimed one \(C = \mathcal {O}\left(2^{0.0885 n}\right)\) . 