Proof. The claim follows from a double-counting argument. Since \(G\) is left-regular of degree \(c\), we have \(c|S| =|E(S,N(S))|\). On the other hand, \[\begin{align} |E(S,N(S))| & =\sum_{i=1}^{d} i|N_i(S)| \\ & \ge |N_{\le t}(S)|+(t+1) (|N(S)|-|N_{\le t}(S)|) \\ & =(t+1)|N(S)|-t|N_{\le t}(S)| \\ & \geq (t+1)\delta c|S|-t|N_{\le t}(S)|, \end{align}\] where the last inequality follows from the expansion property of \(G\).

Therefore, we have \(c|S|\geq (t+1)\delta c|S|-t|N_{\le t}(S)|\). Rearranging this establishes the lemma. ◻

Proof. Since \(G\) is left-regular of degree \(c\), the number of edges incident to \(F \subseteq L\) is \(c|F|\). Each vertex in \(U(x) \subseteq R\) is incident to at least one of these edges. Therefore, \(|U(x)| \leq c|F|\).

Since the minimum distance of \(C_{0}\) is \(d_{0}\), every \(v \in R\) that is a common neighbor of no more than \(d_0 - 1\) vertices in \(F\) must be an unsatisfied check, i.e., \(N_{\leq d_0-1}(F) \subseteq U(x)\). It follows that \(|N_{\leq d_0-1}(F)| \leq |U(x)|\).

Finally, applying 3 with \(t = d_0 - 1\) and \(S = F\) gives the inequality \[|N_{\leq d_0-1}(F)| \geq \frac{\delta d_0 - 1}{d_0 - 1} \cdot c|F|.\qedhere\] ◻

Proof. Since \(G\) is left-regular of degree \(c\), we have \(|E(S,N(S))|=c|S|\). Moreover, by the definition of \(N_{\geq t}(\cdot)\), we have \(|E(S,N(S))|\geq t |N_{\geq t}(S)|\). The lemma follows. ◻

Proof. For any linear code, its distance is equal to the minimum Hamming weight among all of its codewords.

Assume, to the contrary, that \(T(G, C_0)\) has a nonzero codeword \(x\) such that \(\mathrm{wt}(x) \leq \alpha n\). Let \(F = \{i \in [n] : x_i \neq 0\}\), whose size is \(\mathrm{wt}(x)\). By 3, we have \[N_{\leq d_0 - 1}(F) \geq \frac{\delta d_0 - 1}{d_0 - 1} \cdot c |F| > 0.\] This implies that there exists \(u \in R\) that has fewer than \(d_0\) neighbors in \(F\). Consequently, \(\mathrm{wt}(x_{N(u)}) < d_0\).

As the minimum distance of \(C_0\) is \(d_0\), we have \(x_{N(u)} \notin C_0\), which contradicts the assumption that \(x \in T(G, C_0)\). Thus, the lemma is proven. ◻

Proof. Each \(p_i\) is the sum of at most \(\deg(i)=c\) terms of the form \(\frac{t - d_H(w_v, x_{N(v)})}{ct}\), where each term lies between \(0\) and \(\frac{1}{c}\). The lemma follows. ◻

Proof. By the definition of \(F\) and the choice of \(v\), we have \(d_H(y_{N(v)}, x_{N(v)})=k\). As \(y\in T(G, C_0)\), we have \(y_{N(v)}\in C_0\). As \(w_v\) is a vector in \(C_0\) closest to \(x_{N(v)}\), we have \[d_H(w_v, x_{N(v)})\leq d_H(y_{N(v)}, x_{N(v)})=k.\] If \(w_v=y_{N(v)}\), we have \(d_H(w_v, x_{N(v)})=d_H(x_{N(v)}, y_{N(v)})=k\). On the other hand, if \(w_v\neq y_{N(v)}\), then the distance between these two codewords of \(C_0\) is at least \(d_0\), which implies \(d_H(w_v, x_{N(v)})\geq d_H(w_v, y_{N(v)})-d_H(x_{N(v)}, y_{N(v)})\geq d_0-k\). This proves the lemma. ◻

Proof of 5. Let \(F=\{i\in [n]:x_i\neq y_i\}\), whose size is \(d_H(x,y)\leq \alpha n\). By definition, we have \[\label{eq:dh} d_H(x',y) =|F|-|\{i\in F: x_i\text{ is flipped}\}|+|\{i\in [n]\setminus F: x_i \text{ is flipped}\}|.\tag{1}\]

By 1 and linearity of expectation, we have \[\label{eq:dh2} \mathop{\mathrm{\mathbb{E}}}[d_H(x',y)]=|F|-\left(\sum_{i\in F} p_i-\sum_{i\in [n]\setminus F} p_i\right).\tag{2}\]

Consider arbitrary \(v\in R\). In the iteration of the first for loop (Lines 3–9) corresponding to \(v\), some \(p_i\) may increase by \(\frac{t-d_H (w_v,x_{N(v)})}{ct}\). We analyze how this affects the quantity \(\sum_{i\in F} p_i-\sum_{i\in [n]\setminus F} p_i\). Suppose \(v\) has \(k\) neighbors in \(F\), i.e., \(v\in N_k(F)\).

Case 1:

\(k = 0\). In this case, \(d_H(w_v, x_{N(v)}) = 0\). Due to the condition \(1 \leq d_H(w_v, x_{N(v)}) < t\) at Line 5, the iteration corresponding to \(v\) does not affect \(\sum_{i \in F} p_i - \sum_{i \in [n] \setminus F} p_i\).

Case 2:

\(1 \leq k < t\). In this case, we have \(d_H(w_v, x_{N(v)}) = k \in [1, t)\) and \(w_v = y_{N(v)}\) by 8. In the iteration corresponding to \(v\), the index \(i\) chosen at Line 6 is in \(F\) since \(w_v = y_{N(v)}\). Thus, this iteration contributes exactly \[\frac{t - d_H(w_v, x_{N(v)})}{ct} = \frac{t - k}{ct}\] to \(\sum_{i \in F} p_i - \sum_{i \in [n] \setminus F} p_i\).

Case 3:

\(t \leq k< d_0\). In this case, we have \(d_H(w_v, x_{N(v)}) \geq d_0 - k = 2t - k\) by 8. Thus, the iteration corresponding to \(v\) contributes at least \[-\frac{t - d_H(w_v, x_{N(v)})}{ct} \geq -\frac{t - (2t - k)}{ct} = \frac{t - k}{ct}\] to \(\sum_{i \in F} p_i - \sum_{i \in [n] \setminus F} p_i\).

Case 4:

\(k \geq d_0\). In this case, we have \(d_H(w_v, x_{N(v)}) \geq 0\). Thus, the iteration corresponding to \(v\) contributes at least \[-\frac{t - d_H(w_v, x_{N(v)})}{ct} \geq -\frac{t}{ct} \geq \frac{t - k}{ct},\] to \(\sum_{i \in F} p_i - \sum_{i \in [n] \setminus F} p_i\), where the last inequality uses the fact that \(k \geq d_0 = 2t\).

By the above discussion, We have \[\label{eq:sumofpi} \sum_{i\in F} p_i-\sum_{i\in [n]\setminus F} p_i\geq \sum_{k=1}^{d}\frac{t-k}{ct}|N_k(F)|.\tag{3}\]

Next, we establish a lower bound on the RHS of 3 . By the definition of \(N_k(\cdot)\) and the fact that \(G\) is left-regular of degree \(c\), we have \[\label{eq:eq1} \sum_{k=1}^{d} k|N_k(F)|=|E(F,N(F))|=c|F|.\tag{4}\]

As \(|F|\leq \alpha n\) and \(G\) is a \((c,d,\alpha,\delta)\)-bipartite expander, we have \[\label{eq:eq2} \sum_{k=1}^{d} |N_k(F)|=|N(F)|\ge \delta c|F|.\tag{5}\]

Multiplying both sides of 5 by \(t = \frac{1}{\delta} + \varepsilon_0\) and subtracting both sides of 4 , we obtain \[\sum_{k=1}^{d}(t-k)|N_k(F)|\ge \varepsilon_0 \delta c |F|,\] or equivalently, \[\label{eq:eq3} \sum_{k=1}^{d}\frac{t-k}{ct}|N_k(F)|\ge \frac{\varepsilon_0 \delta}{t} |F|.\tag{6}\]

Combining 3 and 6 shows \[\label{eq:eq4} \sum_{i\in F} p_i-\sum_{i\in [n]\setminus F} p_i\geq \frac{\varepsilon_0 \delta}{t} |F|.\tag{7}\] And 2 and 7 together yield \(\mathop{\mathrm{\mathbb{E}}}[d_H(x',y)]\leq (1-\frac{\varepsilon_0\delta}{t})|F|=(1-\frac{\varepsilon_0\delta}{t}) d_H(x,y)\), as desired. ◻

Proof. Consider \(v \in U(x)\) such that the corresponding iteration increases \(p_i\) from zero to nonzero for some \(i \in [n] \setminus F\). By the way \(i\) is chosen at Line 6, we know \(w_v\) and \(x_{N(v)}\) differ at this bit. As \(i \in [n] \setminus F\), we know \(x_{N(v)}\) and \(y_{N(v)}\) agree at this bit. So \(w_v \neq y_{N(v)}\). By 8, this occurs only if \(v \in N_{\geq t}(F)\). Finally, by 5, the number of \(v \in N_{\geq t}(F)\) is at most \(\frac{c}{t}|F|\). ◻

Proof of 6. Let \(t=\frac{d_0}{2}\), \(\varepsilon_1=\frac{\varepsilon_0 \delta}{t}\), and \(\varepsilon_2=\frac{c}{t}\). Let \(\beta\in (0,1)\) be a small enough constant depending only on \(\varepsilon_1\) and \(\varepsilon_2\). We consider two phases of the algorithm:

Phase 1: Many corrupt bits.

Suppose at some point during the algorithm, calling \(\mathsf{RandFlip}(x)\) changes \(F(x,y)\) from a set \(F\) to another set \(F'\), and \(|F|\geq n^\beta\).Then \[|F'|=|F|-\left(\sum_{i\in F} X_i-\sum_{i\in [n]\setminus F}X_i\right),\] where each \(X_i\) is the indicator random variable associated with the event that \(x_i\) is flipped in \(\mathsf{RandFlip}(x)\). Each \(X_i\) takes the value one with probability \(p_i\) (see 1) and zero with probability \(1-p_i\), and these random variables \(X_i\) are independent. Also note that by 9, the number of \(i\in [n]\) such that \(p_i\neq 0\) is at most \((1+\varepsilon_2) |F|\). Let \(\mu=\mathop{\mathrm{\mathbb{E}}}[\sum_{i\in F} X_i-\sum_{i\in [n]\setminus F}X_i]\). By 5, we have \(\mu\geq \varepsilon_1 |F|\). Choose \(k\coloneq\lceil\frac{\log(n^{1-\beta})}{-\log\left(1-\frac{\varepsilon_1}{2}\right)}\rceil\) so that \(n\cdot \left(1-\frac{\varepsilon_1}{2}\right)^k\leq n^\beta\). We have \[\begin{align} \Pr\left[|F'|\geq (1-\frac{\varepsilon_1}{2}) |F|\right]&\leq \Pr\left[\sum_{i\in F} X_i-\sum_{i\in [n]\setminus F}X_i\leq \mu-\frac{\varepsilon_1|F|}{2}\right]\\ &\leq \exp\left(-\frac{2\left(\frac{\varepsilon_1}{2}|F|\right)^2}{(1+\varepsilon_2) |F|}\right) &{(\text{Hoeffding's inequality})}\\ &\leq \exp\left(-\frac{\varepsilon_1^2}{2(1+\varepsilon_2)}n^\beta\right) &{(\text{since }|F|\geq n^\beta)}\\ &=o(1/k). \end{align}\]

Thus, with probability at least \(1-o(1/k)\), the size of \(F(x,y)\) decreases by at least a factor of \(1-\frac{\varepsilon_1}{2}\). By the union bound, with probability \(1-o(1)\), \(|F(x,y)|\) decreases by at least a factor of \(1-\frac{\varepsilon_1}{2}\) in each run of \(\mathsf{RandFlip}(x)\) until \(|F(x,y)|\leq n \cdot \left(1-\frac{\varepsilon_1}{2}\right)^k\leq n^\beta\). When this happens, the total time it takes is \(O\left(\sum_{i=0}^{k-1}\left(n\cdot \left(1-\frac{\varepsilon_1}{2}\right)^i\right)\right)=O(n)\) by 10.

Phase 2: Few corrupt bits.

Now assume \(|F(x,y)|\leq n^\beta\). Consider running \(\mathsf{RandFlip}(x)\) another \(\ell:=\lceil\frac{2\beta \log n}{-\log(1-\varepsilon_1)}\rceil\) times. By 9, the size of \(F(x,y)\) may increase by at most a factor of \(1+\varepsilon_2\) each time. Therefore, \(|F(x,y)|\) would not exceed \[\begin{align} n^\beta \cdot (1+\varepsilon_2)^\ell\le n^{0.5} <\alpha n, \end{align}\] where we use the fact that \(\beta\) is a small enough constant depending on \(\varepsilon_1\) and \(\varepsilon_2\). In particular, as \(|F(x,y)|\leq \alpha n\), 5 applies to each run of \(\mathsf{RandFlip}(x)\), which shows that the expectation of \(|F(x,y)|\) after running \(\mathsf{RandFlip}(x)\) \(\ell\) times is at most \[p\coloneq n^{\beta}\cdot (1-\varepsilon_1)^\ell\leq n^{-\beta}=o(1).\] As the algorithm outputs \(y\) whenever \(|F(x,y)|=0\), by Markov’s inequality, the probability that the algorithm does not output \(y\) after running \(\mathsf{RandFlip}(x)\) \(\ell\) times is \(o(1)\). And the running time of this phase is \(O(\ell n^{0.5})=o(n)\) by 10.

Combining the two phases shows that with probability \(1-o(1)\), 2 correctly outputs \(y\) in \(O(n)\) time. ◻

Proof. Assume to the contrary that \(W\) does not contain any \(q\) satisfying the lemma. In other words, for every \(q\in W\setminus\{0\}\), it holds that \[\label{eq:lessthan} |P_q\cap F|-|P_q\setminus F|< \frac{\varepsilon_0 \delta }{2c t^2}|F|\tag{8}\] Then we have \[\begin{align} \sum_{i\in F} p_i - \sum_{i\in [n]\setminus F} p_i&=\sum_{q\in W}q\left(|P_q\cap F|-|P_q\setminus F|\right)\\ &\leq \sum_{q\in W\setminus\{0\}} \left(|P_q\cap F|-|P_q\setminus F|\right)\\ &< (|W|-1) \frac{\varepsilon_0 \delta }{2c t^2}|F|\\ &\leq \frac{\varepsilon_0 \delta }{t}|F| \end{align}\] where the last two inequalities hold by 8 and the fact that \(|W|-1=cd_0=2ct>0\). On the other hand, we know \(\sum_{i\in F} p_i-\sum_{i\in [n]\setminus F} p_i\geq \frac{\varepsilon_0 \delta}{t} |F|\) (see 7 in the proof of 5). This is a contradiction. ◻

Proof. Suppose the output value \(x_{\min}\) is assigned \(x^{(s)}\) at Line 12 in the iteration corresponding to \((q_1,\dots,q_s)\in (W\setminus\{0\})^s\). We have \(x^{(0)}=x\), \(x^{(i)}=\mathsf{DeterFlip}(x^{(i-1)}, q_i)\) for \(i\in [s]\), and \(x_{\min}=x^{(s)}\).

As \(x^{(0)}=x\), we have \(|F(x^{(0)},y)|=|F(x,y)|\leq \gamma n\leq \frac{d_0-1}{\delta d_0 -1} \gamma n\). Now, consider \(i\in [s]\) and assume \(|F(x^{(i-1)},y)|\leq \frac{d_0-1}{\delta d_0 -1} \gamma n\). By 12, \[|F(x^{(i)},y)|\leq \left(1+\frac{c}{t}\right)|F(x^{(i-1)},y)|\leq \left(1+\frac{c}{t}\right)\frac{d_0-1}{\delta d_0 -1} \gamma n=\alpha n.\] By 4, we have \[\label{eq:u-and-f} |U(x^{(i)})|\ge \frac{\delta d_0 -1}{d_0 - 1} \cdot c |F(x^{(i)},y)|.\tag{9}\] If \(|F(x^{(i)},y)|>\frac{d_0-1}{\delta d_0 -1} \gamma n\), then by 9 , we would have \(|U(x^{(i)})|>c\gamma n\). In this case, the algorithm would exit the inner loop at Line 9 and modify \((q_1,\dots,q_s)\) to a different sequence, contradicting the choice of \((q_1,\dots,q_s)\). Therefore, \(|F(x^{(i)},y)|\leq \frac{d_0-1}{\delta d_0 -1} \gamma n\).

By induction, it follows that \(|F(x^{(i)},y)|\leq \frac{d_0-1}{\delta d_0 -1} \gamma n\) for \(i=0,1,\dots,s\). Choosing \(i=s\) proves the lemma. ◻

Proof. By 1, there exists \((q_1,\dots,q_s)\in (W\setminus\{0\})^{s}\) such that for \((x^{(0)},\dots,x^{(s)})\) defined by \(x^{(0)}=x\) and \(x^{(i)}=\mathsf{DeterFlip}(x^{(i-1)}, q_i)\), we have \(|F(x^{(i)},y)|\leq \left(1-\frac{\varepsilon_0 \delta}{2ct^2}\right)^i|F(x,y)|\) for \(i\in [s]\). By 4, we have \(|U(x^{(i)})|\leq c|F(x^{(i)},y)|\leq c|F(x,y)| \leq c\gamma n\) for \(i\in [s]\). Therefore, the iteration of the outer loop corresponding to \((q_1,\dots,q_s)\) passes the test at Line 8 for \(i\in [s]\) and reaches Line 12.

The element \(x'=x_{\min}\) is chosen to minimize the number of unsatisfied checks among all branches that reach Line 12. So we have \[\label{eq:boundU} |U(x')|\leq |U(x^{(s)})|\leq c|F(x^{(s)},y)|\leq c\left(1-\frac{\varepsilon_0 \delta}{2ct^2}\right)^s|F(x,y)|.\tag{10}\] By 14, we have \(|F(x',y)|\leq \frac{d_0-1}{\delta d_0 -1} \gamma n\leq \alpha n\). So 4 applies to \(x'\) and \(y\). Finally, \[|F(x',y)|\leq \frac{d_0-1}{\delta d_0-1} \cdot \frac{1}{c}\cdot |U(x')|\leq \frac{d_0-1}{\delta d_0-1} \left(1-\frac{\varepsilon_0 \delta}{2ct^2}\right)^s |F(x,y)|\leq \frac{1}{2}|F(x,y)|\] where the first inequality holds by 4, the second one holds by 10 , and the last one holds by the choices of \(s\).

Next, we bound the time complexity. Since \(|W\setminus\{0\}|=c d_0=O(1)\) and \(s=O(1)\), by 12 and 13, the running time is bounded by: \[O\left((cd_0)^s\cdot s\left(1+\frac{c}{d_0/2}\right)^s|F(x,y)|\right)=O(|F(x,y)|).\qedhere\] ◻

Proof. We first prove the correctness of 5. Let \(x\in\mathbb{F}_2^n\) and \(y\in T(G, C_0)\) such that \(d_H(x,y)\leq \alpha n\).

By 1, there exists a sequence \((q_1,\dots q_r) \in (W\setminus\{0\})^r\) such that after completing the first inner loop (Lines 5–7) with respect to this sequence, we have \(|F(\hat{x}, y)|\leq \gamma n\). Fix this sequence \((q_1,\dots q_r)\) and consider the corresponding iteration of the outer loop (assuming it is executed). By 7, \(|F(\hat{x},y)|\) is reduced by at least half each time we apply \(\hat{x}\gets \mathsf{DeepFlip}(\hat{x})\) (Line 9). By 4, for \(i\in [r']\), we have \(|U(\hat{x})|\leq c|F(\hat{x},y)|\leq c 2^{-i} \gamma n\) at Line 10 in the \(i\)-th iteration of the second inner loop (Lines 8–13), which guarantees that the algorithm does not exit this inner loop at line 12. Finally, after completing the second inner loop, \(|F(\hat{x}, y)|\) will be reduced to at most \(2^{-r'} \gamma n<1\), which implies that \(F(\hat{x}, y)=0\) and hence \(\hat{x}=y\). So \(y\) is output at Line 15.

This is assuming that the iteration corresponding to \((q_1,\dots q_r)\) is executed. However, the algorithm may terminate at Line 15 earlier and output some \(\hat{x}\in \mathbb{F}_2^n\) satisfying \(|U(\hat{x})|=0\) and \(d_H(x, \hat{x}) \leq \alpha n\). The former condition means \(\hat{x}\in T(G, C_0)\). In this case, the output is still \(\hat{x}=y\) since \(\alpha n\) is less than half of the minimum distance of \(T(G,C_0)\) [14]. This proves the correctness of 5.

Next, we bound the time complexity. Note that \(r,r',|W\setminus\{0\}|=O(1)\). By 13, the first inner loop runs in \(O(n)\) time. The condition on \(|U(\hat{x})|\) at Line 10 ensures that at the end of the \(i\)-th iteration of the second inner loop, we have \(|U(\hat{x})|\leq c 2^{-i} \gamma n\) and, consequently, \(|F(\hat{x},y)|\leq d|U(\hat{x})|\leq dc 2^{-i} \gamma n\). By 7, the second inner loop also runs in \(O(n+\sum_{i=1}^{r'} dc 2^{-i} \gamma n)=O(n)\) time. It follows that 5 runs in \(O(n)\) time. ◻

Proof. Let \(\delta' =\frac{1}{d_0} + \varepsilon\), \(k= f_\delta^{-1}\left(\delta'\right)\), and \(\alpha' =k \alpha\). By [lem:size95expansion95prop], \(f_{\delta}^{-1}(\delta')\) is well-defined.

Since \(G\) is a \((c,d,\alpha,\delta)\)-bipartite expander and \(k\alpha =\alpha', f_\delta(k)=\delta'\), applying 15 implies that \(G\) is also a \((c,d,\alpha', \delta')\)-bipartite expander. By 6 and the fact that \(\delta' d_0=1+d_0\varepsilon>1\), we have that the distance of \(T(G, C_0)\) is greater than \(\alpha'\), thus proving this theorem. ◻

Proof. Let \(\delta' = \frac{2}{d_0} + \varepsilon\), \(k= f_\delta^{-1}\left(\delta'\right)\), and \(\alpha'= k \alpha\). By [lem:size95expansion95prop], \(f_{\delta}^{-1}(\delta')\) is well-defined.

Since \(G\) is a \((c,d,\alpha,\delta)\)-bipartite expander and \(k\alpha =\alpha', f_\delta(k)=\delta'\), applying 15 implies that the graph \(G\) is also a \((c, d, \alpha', \delta')\)-bipartite expander. Since \(\delta' d_0 = 2 + d_0 \varepsilon> 2\), it follows from 6 and 8 that 2 and 5 can both decode up to \(\alpha' n\) errors in linear time. ◻

Proof. We denote the left and right parts of a bipartite graph \(G\) by \(L(G)\) and \(R(G)\), respectively. Let \(k= f_\delta^{-1}\left(\frac{1}{d_0}\right)\).

We construct two bipartite graphs:

• \(G_0\) is a uniformly chosen random \((c,d_0)\)-regular graph with \(|L(G_0)| = k \alpha n\) and \(|R(G_0)| = c n \frac{k\alpha}{d_0}\).

• \(G_1\) is a uniformly chosen random graph subject to the constraints that (1) \(G_1\) is left-regular of degree \(c\) with \(|L(G_1)| = (1 - k\alpha)n\) and \(|R(G_1)| = c n\frac{1}{d}\), and (2) \(c n \frac{k\alpha}{d_0}\) right vertices of \(G_1\) have degree \(d - d_0\), while the remaining ones have degree \(d\). The parameter \(\alpha\) is chosen to satisfy \(\alpha\leq \frac{d_0}{dk}\) so that this is possible.

We formalize the algorithm used to generate the regular graphs \(G_0\) and \(G_1\) as 10 in 7.1.

Next, we merge \(G_0\) and \(G_1\) into a single bipartite graph \(G\). Specifically, for each vertex \(u \in R(G_0)\), we pair it with a vertex \(v\in R(G_1)\) of degree \(d - d_0\), merging \(u\) and \(v\) into a single vertex. All other vertices in \(G_0\) and \(G_1\) remain unchanged. This process results in the final graph \(G\).

Assume without loss of generality that \(1^{d_0}0^{d-d_0}\in C_0\). Then, for each merged vertex \(v\in R(G)\), we may order its \(d\) neighbors such that the first \(d_0\) neighbors are in \(L(G_0)\). Then the unique vector in \(\mathbb{F}_2^{L(G)}\) with support \(L(G_0)\) is a codeword of \(T(G,C_0)\), implying that the minimum distance of \(T(G, C_0)\) is at most \(|L_0(G)|=k\alpha n\).

It remains to prove that \(G\) is a \((c,d,\alpha,\delta - \varepsilon)\)-bipartite expander with high probability. Fix a set \(S \subseteq L(G)\) with \(|S| \leq \alpha n\). Let \(S_0 \mathrel{\vcenter{:}}= S \cap L(G_0)\) and \(S_1 \mathrel{\vcenter{:}}= S \cap L(G_1)\). Suppose \(|S_0| = \alpha_0 n\) and \(|S_1| = \alpha_1 n\), where \(\alpha_0 + \alpha_1 \eqcolon\alpha'\leq \alpha\). Next, we bound the probability that \(N(S)\) is small.

5.3.0.1 Bounding the probability when \(S\) is large.

Assume \(\gamma n\le |S|\le \alpha n\), where \(\gamma=O_{\delta,\alpha,d_{0},d}(1)\) is a small constant to be determined later. Denote the set of merged vertices in \(R(G)\) as \(M\). We calculate the expected size of \(N(S)\) using Azuma’s inequality. \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[|N(S)|] & =\notag \sum_{u \in R(G)} \Pr[u \in N(S)] \\ & =\notag |R(G)|-\sum_{u \in R(G), u \in M} \Pr[u \not\in N(S)] -\sum_{u \in R(G), u\not \in M} \Pr[u \not\in N(S)] \\ & \geq c n \left(\frac{1}{d} - \frac{k\alpha}{d_0} \left(1 - \frac{\alpha_0}{k\alpha}\right)^{d_0} \left(1 - \frac{\alpha_1}{1 - k\alpha}\right)^{d-d_0} - \left(\frac{1}{d} - \frac{k\alpha}{d_0}\right)\left(1 - \frac{\alpha_1}{1 - k\alpha}\right)^{d}\right),\label{ineq:expected95neibors1} \end{align}\tag{14}\] where the last step holds since for \(u\in R(G)\), \[\Pr[u \not\in N(S)]\leq\begin{cases} \left(1 - \frac{\alpha_0}{k\alpha}\right)^{d_0} \left(1 - \frac{\alpha_1}{1 - k\alpha}\right)^{d-d_0} & u\in M, \\ \left(1 - \frac{\alpha_1}{1 - k\alpha}\right)^{d} & u\not\in M. \end{cases}\]

We claim 14 is bounded from below by \[\begin{align} & c n\left(\frac{1}{d} - \frac{k\alpha}{d_0} \left(1 - \delta d_0 \frac{\alpha_0}{k\alpha}\right) - \left(\frac{1}{d} - \frac{k\alpha}{d_0}\right)(1 - \alpha_1 d+O_{k,d,d_0}(\alpha'^2))\right) \tag{15} \\ & = c n \left(\delta \alpha_0 + \alpha_1 - O_{k,d,d_0}( \alpha'^2)\right).\tag{16} \end{align}\] To see this, we first prove the following claim.

By the convexity of the function \(g(x)\mathrel{\vcenter{:}}= (1-x)^{d_{0}}\) for \(x\in [0,1]\), we know that \[\left( 1 - \frac{\alpha_0}{k \alpha} \right)^{d_0} =g\left(\frac{\alpha_{0}}{k \alpha }\right)\le \left(1-\frac{\alpha_{0}}{\alpha } \right) g(0)+\frac{\alpha_{0}}{\alpha }g\left(\frac{1}{k}\right)=1-\frac{\alpha_0}{\alpha}+\frac{\alpha_0}{\alpha}(1-\frac{1}{k})^{d_0}\le 1 - \delta d_0 \frac{\alpha_0}{k \alpha}, \label{ineq:expected95neibors3}\tag{18}\] where the last inequality holds by 12. By 18 , we see that 14 , and consequently \(\mathop{\mathrm{\mathbb{E}}}[|N(S)|]\), is bounded from below by 15 .

By choosing \(\alpha\geq \alpha'\) to be sufficiently small (but still a constant depending on \(k,d,d_0,\varepsilon\)), we can ensure that the term \(O_{k,d,d_0}(\alpha'^2)\) in 16 is at most \(\alpha' \frac{\varepsilon}{2}\). Thus, as \(|S|=\alpha_0 n+\alpha_1 n=\alpha' n\), we have

\[\mathop{\mathrm{\mathbb{E}}}[|N(S)|] \geq c n \left(\delta \alpha_0 + \alpha_1 - \alpha' \frac{\varepsilon}{2}\right)\geq \left(\delta - \frac{\varepsilon}{2}\right)c|S|.\]

Now, consider the process of revealing the edges going out of \(S\) one by one, in an arbitrary order. For \(i=0,1,\dots, c|S|\), let \[X_i=\mathop{\mathrm{\mathbb{E}}}[|N(S)| \mid \text{The first }i\text{ edges going out of }S\text{ are revealed}].\] Clearly, the random variables \(X_i\) form a martingale, and \(|X_{i+1} - X_i| \leq 1\). By Azuma’s inequality (2), for any \(\lambda>0\), \[\begin{align} \Pr[|X_{c|S|} - X_0| \geq \lambda] \leq 2\exp\left(-\frac{\lambda^2}{2 c|S|}\right). \end{align}\]

Choose \(\lambda = \sqrt{\log \left(2n^2\binom{n}{|S|}\right)\cdot2c|S|} =O\left(\sqrt{c|S|\log n+ c|S|^2\log \frac{1}{\gamma } } \right)= O_{\gamma }(\sqrt{c}|S|)\). Also choose sufficiently large \(c=\Omega_{\gamma }(\frac{1}{\varepsilon^2})\) such that \(\lambda\leq \frac{\varepsilon}{2} c|S|\). Then we have \[\begin{align} \Pr[|N(S)| \leq (\delta - \varepsilon)c |S|] \leq \Pr\left[||N(S)|-\mathop{\mathrm{\mathbb{E}}}[|N(S)|]|\geq \lambda\right] \leq \left(n^2 \binom{n}{|S|}\right)^{-1}.\label{ineq:prob95large95s} \end{align}\tag{19}\]

5.3.0.2 Bounding the probability when \(S\) is small.

Assume \(1\le |S|< \gamma n\). We claim that with high probability, \(|N(S)|\ge\delta c|S|\). By the union bound, \[\begin{align} \Pr[|N(S)|\le \delta c|S|] & \le \sum_{\substack{T\subseteq R(G),\\|T|=\delta c|S|}}\Pr[N(S)\subseteq T]\\ & \le \binom{\frac{c}{d}n}{\delta c|S|} \cdot \max\left\{\frac{d\cdot \delta c|S|}{cn k\alpha}, \frac{d\cdot \delta c|S|}{(1-k \alpha )n c}\right\}^{c|S|}\\ &=\binom{\frac{c}{d}n}{\delta c|S|} \cdot \max\left\{\frac{d\cdot \delta |S|}{n k\alpha}, \frac{d\cdot \delta |S|}{(1-k \alpha )n }\right\}^{c|S|}, \end{align}\] where \(\max\left\{\frac{d\cdot \delta c|S|}{cn k\alpha}, \frac{d\cdot \delta c|S|}{(1-k \alpha )n c}\right\}^{c|S|}\) is an upper bound on \(\Pr[N(S) \subseteq T]\).

Using the standard estimate \(\binom{n}{m}\leq \left(\frac{ne}{m}\right)^m\), we obtain \[\begin{align} \Pr[|N(S)|\le \delta c|S|] & \le \left(\frac{ne}{d\delta |S|}\right)^{\delta c|S|}\cdot \max\left\{\frac{d\cdot \delta |S|}{n k\alpha}, \frac{d\cdot \delta |S|}{(1-k \alpha )n }\right\}^{c|S|}\\ & = \left(O_{\delta,\alpha,d_{0},d}(1)\cdot \left(\frac{|S|}{n}\right)^{1-\delta }\right)^{c|S|} \end{align}\] Choose \(\gamma\) to be a sufficiently small constant depending on \(\delta\), \(\alpha\), \(d_{0}\), and \(d\). And choose \(c\) to be a sufficiently large constant depending on \(\delta\).⁶ We have \[\begin{align} \Pr[|N(S)|\le \delta c|S|] \le \left(O_{\delta,\alpha,d_{0},d}(1)\cdot \gamma^\frac{1-\delta}{2}\left(\frac{|S|}{n}\right)^\frac{1-\delta}{2} \right)^{c|S|} \leq \left(\frac{|S|}{en}\right)^{\frac{1-\delta}{2}c|S|} \leq \left(\frac{|S|}{en}\right)^{2|S|}. \label{ineq:prob95small95s} \end{align}\tag{20}\]

5.3.0.3 Union bound.

Combining the bounds 19 and 20 and taking the union bound over all \(S\), we see that the probability that \(|N(S)|\geq (\delta-\varepsilon) c|S|\) for all \(S\subseteq L(G)\) of size at most \(\alpha n\) is at least \[\begin{align} 1 & -\Pr[\exists\,S \subseteq L(G) \text{ such that } |S|\in [\gamma n, \alpha n] \text{ and } |N(S)|\le (\delta-\varepsilon)c|S|] \\ & -\Pr[\exists\,S\subseteq L(G)\text{ such that } |S|\in [1,\gamma n) \text{ and } |N(S)|\le (\delta-\varepsilon)c|S|]\cr & \ge 1- \sum_{i=\gamma n}^n\binom{n}{i}\left(n^2\binom{n}{i}\right)^{-1}-\sum_{i=1}^{\gamma n-1}\binom{n}{i}\left(\frac{i}{en}\right)^{2i}\cr &\ge 1- \sum_{i=\gamma n}^n\binom{n}{i}\left(n^2\binom{n}{i}\right)^{-1}-\sum_{i=1}^{\gamma n-1}\left(\frac{ne}{i}\right)^i\left(\frac{i}{en}\right)^{2i}\cr & \ge 1-o(1). \end{align}\] Therefore, \(G\) is a \((c,d,\alpha,\delta-\varepsilon)\)-bipartite expander with high probability. ◻

Proof. The ratio can be expressed as: \[\frac{\binom{km-i}{m}}{\binom{km}{m}} = \frac{(km-i)(km-i-1) \ldots((k-1)m-i+1)}{km(km-1) \ldots((k-1)m+1)}.\] Since the product \((km-i)\cdots((k-1)m+1)\) appears in both the numerator and denominator, by factoring out the \(\left(1 - \frac{1}{k}\right)\) terms, we can simplify the ratio as follows: \[\frac{\binom{km-i}{m}}{\binom{km}{m}} =\prod_{j=0}^{i-1}\frac{(k-1)m-j}{km-j} =\left( 1-\frac{1}{k} \right)^i\cdot \prod_{j=0}^{i-1}\left(1-\frac{j}{(k-1)(km-j)}\right)\leq \left(1 - \frac{1}{k}\right)^i.\] Further, we bound the additional factor: \[\begin{align} \prod_{j=0}^{i-1}\left(1-\frac{j}{(k-1)(km-j)}\right) & \ge 1-\sum_{j=0}^{i-1}\frac{j}{(k-1)(km-j)} \\ & \ge 1-\frac{i(i-1)}{2(k-1)(km-i)} . \end{align}\] Therefore, we have \[\begin{align} \frac{\binom{km-i}{m}}{\binom{km}{m}} & \ge \left(1 - \frac{1}{k}\right)^i \left( 1-\frac{i(i-1)}{2(k-1)(km-i)} \right) \\ & \ge \left(1 - \frac{1}{k}\right)^i- \frac{i(i-1)}{2(k-1)(km-i)} \\ & = \left(1 - \frac{1}{k}\right)^i - O_{k,i}\left(\frac{1}{m}\right). \end{align}\] This completes the proof. ◻

Proof. We prove these properties separately.

7.3.0.1 Monotonicity.

Let \(k' > k\), and let \((\hat{\beta_i})_{i\in\mathbb{N}^+}\) denote the optimal solution to the LP defining \(f_{\delta}(k)\). Then, \((\frac{k'}{k} \hat{\beta_i})_{i\in\mathbb{N}^+}\) is a feasible solution to the LP defining \(f_{\delta}(k')\), and the corresponding value of the objective function is \[\frac{1}{k'}\sum_{i=1}^\infty \frac{k'}{k} \hat{\beta_i}=\frac{1}{k}\sum_{i=1}^\infty\hat{\beta_i}=f_{\delta}(k).\] Therefore, \(f_{\delta}(k')\leq f_{\delta}(k)\). The same argument applies to \(f_{d,\delta}\). This proves [p1].

7.3.0.2 Relation between \(f_\delta\) and \(f_{d,\delta}\).

Recall the definition of \(f_{\delta}(k)\) from 5, which is the minimum of the following LP: \[\begin{align} \text{minimize} \quad & \frac{1}{k} \sum_{i=1}^{\infty} \beta_i \\ \text{subject to} \quad & \sum_{i=1}^{\infty} i \cdot \beta_i = k, \\ & \sum_{i=1}^{\infty} \left(1 - \left(1 - \frac{1}{k}\right)^i\right) \cdot \beta_i \ge \delta, \\ & \beta_i \ge 0, \quad \forall i. \end{align} \label{eq:LP}\tag{21}\]

We now show that the optimal solution is achieved by \(\hat{\beta}=(\hat{\beta}_i)_{i\in\mathbb{N}^+}\) that is supported on at most two adjacent indices. The proof follows [12].

The dual of this LP is: \[\begin{align} \text{maximize} \quad & kx + \delta y \\ \text{subject to} \quad & x \cdot i + y \left(1 - \left(1 - \frac{1}{k}\right)^i\right) \le \frac{1}{k}, \quad \forall i \in \mathbb{N}^+ \\ & y \ge 0. \end{align} \label{eq:DP}\tag{22}\]

Assume, for contradiction, that \(\hat{\beta}_i, \hat{\beta}_j \neq 0\) with \(j > i + 1\). By the complementary slackness conditions, the corresponding constraints in Equation 22 must be satisfied as equalities: \[x \cdot i + y \left(1 - \left(1 - \frac{1}{k}\right)^i\right) = \frac{1}{k}\] and \[x \cdot j + y \left(1 - \left(1 - \frac{1}{k}\right)^j\right) = \frac{1}{k}.\] These two equalities imply that \(y \neq 0\).

The function \(1 - \left(1 - \frac{1}{k}\right)^i\) is convex with respect to \(i\). In particular: \[\left(1 - \left(1 - \frac{1}{k}\right)^i\right) - \left(1 - \left(1 - \frac{1}{k}\right)^{i-1}\right) > \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right) - \left(1 - \left(1 - \frac{1}{k}\right)^i\right).\] From the two equalities derived from the slackness conditions, \(y > 0\), and the convexity of the function, we obtain: \[x \cdot (i + 1) + y \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right) > \frac{1}{k}.\] This contradicts the constraints of the dual program. Thus, we have shown that \(\hat{\beta}\) must be supported on at most two adjacent indices.

Now, assume that the support of \(\hat{\beta}\) is contained in \(\{i,i+1\}\) for some \(i\in\mathbb{N}^+\). Then, the LP 21 simplifies to: \[\begin{align} \text{minimize} \quad & \frac{1}{k}(\beta_i + \beta_{i+1}) \\ \text{subject to} \quad & \beta_i \cdot i + \beta_{i+1} \cdot (i+1) = k, \\ & \beta_i \cdot \left(1 - \left(1 - \frac{1}{k}\right)^i\right) + \beta_{i+1} \cdot \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right) \ge \delta, \\ & \beta_i, \beta_{i+1} \ge 0. \end{align}\]

The optimal value of this problem is given by: \[\begin{align} \begin{cases} \frac{\delta - (1 - \frac{1}{k})^i}{k - (k + i)(1 - \frac{1}{k})^i}, \quad & \text{for } \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right)}{i+1} \le \delta \le \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^i\right)}{i}, \\ \frac{1}{i+1}, \quad & \text{for } \delta < \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right)}{i+1}, \\ \text{infeasible}, \quad & \text{otherwise}. \end{cases} \end{align}\]

By comparing the values above for different choices of \(i\), we find the value of \(f_{\delta}(k)\) is given by: \[\label{eq:f95delta95expr} f_\delta(k) = \frac{\delta - (1 - \frac{1}{k})^i}{k - (k + i)(1 - \frac{1}{k})^i} \quad\text{for } i\in\mathbb{N}^+ \text{ such that } \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right)}{i+1} \le \delta \le \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^i\right)}{i}.\tag{23}\]

The same analysis applies to the LP defining \(f_{d,\delta}\), with the only difference being that the choice of \(i\) is restricted to the range \([d-1]\). Therefore, we have the expression for \(f_{d,\delta}(k)\) as follows: \[\label{eq:f95d95delta95expr} f_{d,\delta}(k) = \begin{cases} \frac{1}{d}, \quad & \text{for } \delta < \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^d\right)}{d}, \\ \frac{\delta - (1 - \frac{1}{k})^i}{k - (k + i)(1 - \frac{1}{k})^i}, \quad & \text{for } i\in [d-1] \text{ such that } \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right)}{i+1} \le \delta \le \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^i\right)}{i}. \end{cases}\tag{24}\]

Next, we consider the condition \(f_\delta(k) \neq f_{d,\delta}(k)\), which implies that the support of the optimal solution \(\hat{\beta}\) of the LP 21 has the form \(\{i+1\}\) or \(\{i,i+1\}\) with \(i\geq d\). Therefore, comparing 24 with 23 proves [p2].

7.3.0.3 Improvement over the trivial bound \(\frac{\delta}{k}\).

By substituting \(x = 0\) and \(y = \frac{1}{k}\) into the dual program 22 , we see that \(f_{\delta}(k)\geq \frac{\delta}{k}\), which establishes [p3].

7.3.0.4 Effect of omitting the \(O\left(\frac{1}{n}\right)\) term.

Let \(f^*_{d,\delta}(k)\) be the size-expansion trade-off defined by the LP without omitting the error term. The only difference from the LP defining \(f_{d,\delta}(k)\) is that the constraint becomes \(\sum_{i=1}^{d} \left(1 - \left(1 - \frac{1}{k}\right)^i\right) \beta_i \ge \delta - O\left(\frac{1}{n}\right)\), and the dual objective function changes to \(kx + \left(\delta - O\left(\frac{1}{n}\right)\right)y\).

Let \((\hat{x}, \hat{y})\) be the optimal solution for the dual program for \(f_{d,\delta}(k)\), so \(f_{d,\delta}(k) = k\hat{x} + \delta \hat{y}\). Since \(\hat{x}, \hat{y}\) also satisfy the dual program for \(f^*_{d,\delta}(k)\), we obtain the bound: \[f^*_{d,\delta}(k) \ge f_{d,\delta}(k) - \hat{y}\cdot O\left( \frac{1}{n} \right).\]

Next, we bound \(\hat{y}\). The constraint in 22 with \(i = 1\) states that \(\hat{x} + \frac{\hat{y}}{k} \le \frac{1}{k}\), i.e., \(\hat{x} \le \frac{1 - \hat{y}}{k}\). Therefore, \[f_{d,\delta}(k) = k \hat{x} + \delta \hat{y} \le 1 - \hat{y} + \delta \hat{y}.\] By [p3], \(f_{d,\delta}(k)\geq \frac{\delta}{k}\geq 0\). So \(y\leq \frac{1}{1-\delta}=O(1)\). Thus, \(f^*_{d,\delta}(k) \ge f_{d,\delta}(k) - O\left( \frac{1}{n} \right)\), which proves [p4].

7.3.0.5 Continuity and range.

The continuity of \(f_\delta\) can be established via the explicit description of \(f_\delta\) given in 23 . When \(k\) is located at the endpoint of two pieces, namely, when \[\frac{k \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right)}{i+1} = \delta\] for some positive integer \(i\), we have \[\lim_{x \to k^-} f_{\delta}(x) = \frac{\delta - \left(1 - \frac{1}{k}\right)^i}{k - (k + i)\left(1 - \frac{1}{k}\right)^i} = \frac{1}{i+1} = \frac{\delta - \left(1 - \frac{1}{k}\right)^{i+1}}{k - (k + i+1)\left(1 - \frac{1}{k}\right)^{i+1}} = \lim_{x \to k^+} f_{\delta}(x).\] Thus, \(f_\delta\) is continuous.

To prove that \(\lim_{k \to 1} f_{\delta}(k) = \delta\), note that for bounded \(k\), the value of \(i\) chosen in 23 satisfies \(i=O(1/\delta)\). Thus, \[\lim_{k \to 1} f_{\delta}(k)=\lim_{k\to 1} \frac{\delta - (1 - \frac{1}{k})^i}{k - (k + i)(1 - \frac{1}{k})^i} =\lim_{k\to 1}\frac{\delta}{k}=\delta.\]

Next, we prove that \(\lim_{k \to \infty} f_{\delta}(k) = 0\). For any fixed \(i\), we have \[\lim_{k \to \infty} \frac{k \left(1 - \left(1 - \frac{1}{k}\right)^{i+1}\right)}{i+1} = 1.\] Thus, as \(k \to \infty\), the value of \(i\) chosen in 23 also tends to infinity. Therefore, the value of the function satisfies \[\lim_{k \to \infty} f_\delta(k) = \lim_{k \to \infty} \frac{\delta - \left(1 - \frac{1}{k}\right)^i}{k - (k + i)\left(1 - \frac{1}{k}\right)^i} \le \lim_{k \to \infty} \frac{1}{i} = 0,\] which completes the proof of [p5]. ◻

Proof. In the proof, we use \(L'\) and \(R'\) to denote the intermediate sets at any point of executing the algorithm. We prove that the invariant \(|L'|\le \alpha n -1\) is maintained throughout the whole procedure.

If, during the execution of \(\mathsf{FindErasure}(x)\), there are multiple valid choices for the next vertex to be added to \(L'\), the order in which they are added does not affect the final set \(L'\). Indeed, since \(R'\) only grows throughout the algorithm, any vertex \(i\) satisfying \(|N(i)\cap R'|\ge h\) at some point will continue to satisfy this condition until it is added to \(L'\).

Let \[F_0\coloneq \{i\in F: |N(i)\cap U(x)|\ge h\}.\] We choose an order in which all vertices in \(F_0\) are added before any other vertices. This is valid since every vertex in \(F_0\) satisfies the threshold condition at the beginning of the algorithm.

Since \(|F|\le \gamma(\alpha n-1)\) and \(\gamma\le 1\), we have \[|F_0|\le |F|\le \alpha n-1.\] So the invariant holds for \(L'=F_0\).

Every check node in \(U(x)\) has at least one neighbor in \(F\). Therefore, \(|E(F,U(x))|\ge |U(x)|\). On the other hand, every vertex in \(F\setminus F_0\) contributes fewer than \(h\) edges to \(E(F, U(x))\). Hence \[|E(F_0,U(x))|\geq |E(F,U(x))|-h(|F|-|F_0|) \geq|U(x)|-h(|F|-|F_0|).\]

Therefore, the size of \(R'\) after adding all vertices in \(F_0\), denoted by \(R_0\), is bounded by \[\begin{align} |R_0| & = |U(x)\cup N(F_0)| \\ & \le |U(x)|+|N(F_0)\setminus U(x)| \\ & \le |U(x)|+|E(F_0,N(F_0)\setminus U(x))| \\ & \le |U(x)|+c|F_0|-|E(F_0,U(x))| \\ & \le (c-h)|F_0|+h|F|. \label{eq:R0-upper} \end{align}\tag{26}\]

After all the vertices of \(F_0\) have been added, we consider the remaining vertices added to \(L'\) one by one. Whenever a vertex \(i\) is added to \(L'\), it already has at least \(h\) neighbors in \(R'\), and hence at most \(c-h\) new right vertices are added to \(R'\). So we always have \[\label{eq:viderman-R-upper} |R'|\leq |R_0|+(c-h)(|L'|-|F_0|)\leq(c-h)|L'|+h|F|,\tag{27}\] where the second inequality follows from 26 . By the invariant, \(|L'|\le \alpha n-1\) before adding a single vertex. So after that, we still have \(|L'|\leq \alpha n\), and the expansion property gives \[\delta c|L'|\leq |N(L')|\leq |R'|\le(c-h)|L'|+h|F|,\] where the last inequality holds by 27 . Therefore, \[\left(h-c(1-\delta)\right)|L'|\le h|F|.\] As \(|F|\le \gamma(\alpha n-1)\) and \(\gamma=1-\frac{c(1-\delta)}{h}\), we have \[|L'|\le \frac{h|F|}{h-c(1-\delta)} \leq \frac{h\gamma(\alpha n-1)}{h-c(1-\delta)} =\alpha n -1.\] Repeating this argument for each vertex added to \(L'\) shows that the invariant \(|L'|\leq \alpha n-1\) holds throughout the algorithm, and in particular for the final output. ◻

Proof. Let \(R'\) be the final set of right vertices maintained by 11. Suppose for contradiction that \[S\coloneq F\setminus L'\neq \emptyset.\] Since the algorithm has stopped, every \(i\in S\) satisfies \(|N(i)\cap R'|<h\). Thus \[\label{eq:viderman-edge-S-R} |E(S,R')|<h|S|.\tag{28}\] We now upper bound \(|N(S)|\). Consider \(v\in N(S)\setminus R'\). As \(N(L')\subseteq R'\), the check \(v\) has no neighbor in \(L'\). As \(v\in N(S)\subseteq N(F)\) and \(F=F(x,y)\), we have \(x_{N(v)}\neq y_{N(v)}\). On the other hand, as \(U(x)\subseteq R'\), the check \(v\) is satisfied by \(x\), implying that \(x_{N(v)}\) is a codeword of \(C_0\). So \(x_{N(v)}\) and \(y_{N(v)}\) are distinct codewords of \(C_0\). It follows that \[|N(v)\cap F|=|N(v)\cap S|\geq d_0.\] As this holds for all \(v\in N(S)\setminus R'\), we have \[|N(S)\setminus R'|\leq \frac{|E(S,N(S)\setminus R')|}{d_0}=\frac{c|S|-|E(S,R')|}{d_0}.\] It follows that \[\begin{align} |N(S)| & =|N(S)\cap R'|+|N(S)\setminus R'| \\ & \leq |E(S,R')|+\frac{c|S|-|E(S,R')|}{d_0} \\ & =\left(1-\frac{1}{d_0}\right)|E(S,R')| +\frac{c}{d_0}|S| \\ & <\left(\left(1-\frac{1}{d_0}\right)h+\frac{c}{d_0}\right)|S| \\ & =\delta c|S|, \end{align}\] where the strict inequality follows from 28 , and the last equality follows from the definition of \(h\) 25 . On the other hand, since \(S\subseteq F\) and \(|F|\leq \alpha n\), the expansion property gives \(|N(S)|\geq \delta c|S|\), a contradiction. Hence \(F\subseteq L'\). ◻

Proof. We maintain the invariant that \(\hat{x}_i=y_i\) for every \(i\in L\setminus L'\). This invariant holds initially because \(F(x,y)\subseteq L'\).

Suppose \(L'\neq \emptyset\). Since \(|L'|\leq \alpha n\), applying 3 with \(S=L'\) and \(t=d_0-1\) gives \[|N_{\leq d_0-1}(L')|\geq \frac{\delta d_0-1}{d_0-1}\cdot c|L'|>0.\] Thus there exists \(v\in R\) such that \(1\leq |N(v)\cap L'|\leq d_0-1\). In particular, Line 3 of 12 can always be executed whenever \(L'\neq\emptyset\), which is guaranteed by the condition in Line 2.

By the invariant, we have \(\hat{x}_{N(v)\setminus L'}=y_{N(v)\setminus L'}\). Since \(y_{N(v)}\in C_0\), there exists a codeword of \(C_0\) that agrees with \(\hat{x}\) on the unerased coordinates \(N(v)\setminus L'\). This codeword is unique. Indeed, if two distinct codewords of \(C_0\) agreed with \(\hat{x}_{N(v)\setminus L'}\) on the unerased coordinates, then their difference would be a nonzero codeword supported on at most \(|N(v)\cap L'|\le d_0-1\) coordinates, contradicting the minimum distance of \(C_0\). Therefore, \(\mathsf{InnerErasureDecode}(\hat{x}_{N(v)},N(v)\cap L')\) returns \(y_{N(v)}\) and the invariant is preserved after removing \(N(v)\) from \(L'\).

The loop terminates after at most \(|L'|\) iterations, since \(|N(v)\cap L'|\ge 1\) in every iteration and all elements of \(N(v)\cap L'\) are removed from \(L'\). At termination, \(L'=\emptyset\), and the invariant implies that \(\hat{x}=y\).

To achieve the desired running time, maintain the values \(|N(v)\cap L'|\) for all \(v\in R\), together with a queue of checks \(v\) satisfying \(1\leq |N(v)\cap L'|\leq d_0-1\). Whenever erased coordinates are recovered, update only the counts of their neighboring checks. Since \(c\), \(d\), and the local erasure-decoding time of \(C_0\) are constants, each edge of the graph \(G\) is processed only \(O(1)\) times. Therefore, the total running time is \(O(n)\). ◻

Proof of 13. Let \(y\in T(G,C_0)\) be the transmitted codeword, and let \(F=F(x,y)\). Assume \(|F|\leq \gamma(\alpha n-1)\).

By 19, the output \(L'\) of 11 satisfies \(|L'|\leq \alpha n\). Since \(|F|\leq \gamma(\alpha n-1)\) and \(\gamma\leq 1\), we also have \(|F|\leq \alpha n\), and therefore 20 gives \(F\subseteq L'\). Finally, the condition \(\delta>\frac{d_0}{2d_0-1}\) implies \(\delta d_0>1\), so 21 shows that 12 outputs \(y\).

It remains to verify that 11 runs in \(O(n)\) time. We first compute \(U(x)\) by checking every right vertex, which takes \(O(n)\) time. We then maintain the values \(|N(i)\cap R'|\) for all \(i\in L\), together with a queue of vertices in \(L\setminus L'\) satisfying the threshold condition. Whenever a new right vertex is added to \(R'\), we update the counters of its \(d\) left neighbors, adding them to the queue when necessary. When a vertex from the queue is added to \(L'\), it is removed from the queue.

Every left vertex is added to the queue at most once and removed to the queue at most once. Moreover, since each right vertex is added to \(R'\) at most once and \(c,d\) are constants, every edge is processed only \(O(1)\) times. Therefore, 11 runs in \(O(n)\) time. Combined with 21, this implies that the entire decoder runs in \(O(n)\) time. ◻