7 Parallel decoding
Repeat until no such variable remains: in parallel, flip every variable that is in more unsatisfied than satisfied constraints.
Let \(B\) be a \((c,d,\alpha ,(3/4+\epsilon )c)\)-expander, for any \(\epsilon {\gt}0\), and let \(\mathcal{P}\) be the code of all even-weight words of length \(d\). Then the simple parallel decoding algorithm corrects any \(\alpha _0 {\lt} \alpha (1+4\epsilon )/2\) fraction of error after \(\log _{1/(1-4\epsilon )}(\alpha _0 n)\) decoding rounds.
Let \(V\) be the set of corrupt variables in the input, with \(|V| {\lt} \alpha n(1+4\epsilon )/2\). We show that after one round at most \((1-4\epsilon )|V|\) variables are corrupt; iterating then drives the count below \(1\) in \(\log _{1/(1-4\epsilon )}(\alpha _0 n)\) rounds.
Let \(F\) be the corrupt variables that fail to flip in the round and \(C\) the variables that were uncorrupt but become corrupt (wrongly flipped). After the round the corrupt set is \(F \cup C\). Set \(\delta = 3/4+\epsilon \), the expansion factor, so \(\delta {\gt} 3/4+\epsilon \).
Step 1: \(|V \cup C| {\lt} \alpha n\). Suppose not; take a subset \(C' \subseteq C\) with \(|V\cup C'| = \alpha n\). By expansion, \(|N(V\cup C')| \ge (3/4+\epsilon )c\alpha n\). On the other hand every variable in \(C\) has at most \(c/2\) neighbours that are not neighbours of \(V\) (else it would not have been flipped toward corruption), so \(|N(V\cup C')| \le \delta c|V| + c(\alpha n - |V|)/2\). Combining, \(|V| \ge \alpha n(1+4\epsilon )/(4\delta -2)\); since \(\delta \le 1\) this contradicts \(|V| {\lt} \alpha n(1+4\epsilon )/2\). Hence \(|V\cup C| {\lt} \alpha n\).
Step 2: bounding the surviving corrupt set. Since \(|V\cup C| {\lt} \alpha n\), by expansion
Each variable in \(F\) shares at least half of its \(c\) edges with other corrupt variables (it failed to flip), so each variable of \(F\) accounts for at most \((3/4)c\) neighbours, and each variable of \(V\setminus F\) for at most \(c\); hence
Substituting into (2) gives \((3/4+\epsilon )(|V|+|C|) \le |V| - |F|/4 + |C|/2\), i.e.
Thus the number of corrupt variables drops to at most \((1-4\epsilon )|V|\) each round, proving the claim.
For \(c\) and \(d\) constant, the simple parallel decoding algorithm can be implemented as a Boolean circuit of size \(O(n\log n)\) and depth \(O(\log n)\).
Each parallel decoding round is implementable in linear size and constant depth: computing which constraints are unsatisfied is a constant number of layers of xor gates (each constraint has \(d\) inputs, \(d\) constant), and deciding whether a given variable should flip is a majority of a constant number of inputs (the variable’s \(c\) constraints, \(c\) constant). By Theorem 32 there are \(O(\log n)\) rounds, so stacking the rounds gives total size \(O(n\log n)\) and depth \(O(\log n)\).