46.07.03 · information-theory / 07-algebraic-coding-advanced

List Decoding: The Sudan and Guruswami-Sudan Algorithms for Reed-Solomon Codes

shipped3 tiersLean: none

Anchor (Master): Guruswami & Sudan 1999; Sudan 1997; Guruswami, Rudra & Sudan 2002 Essential coding theory Ch. 6-7; Johnson 1962 A new upper bound for error-correcting codes IRE Trans. IT-8 203-207

Intuition Beginner

You send a message encoded as a polynomial. An attacker corrupts some of the polynomial's values. Standard decoding can correct up to half the minimum distance of the code — if the code can detect $d$ errors, it can correct $d /2$ .

But what if more than $d /2$ errors occur? Standard decoding gives up. List decoding does not: instead of returning a single answer, it returns a short list of all codewords close to the received word. If the list has only one element, you have your answer. If it has several, you use additional context to pick the right one.

The key insight is geometric. Think of the received word as a cloud of points in the plane. Each codeword is a curve passing through the cloud. Standard decoding finds the unique curve closest to the cloud. List decoding finds all curves within a certain distance.

Sudan's algorithm works by fitting a bivariate polynomial $Q (X, Y)$ through all the received points. This polynomial vanishes at every received point. Then, every transmitted polynomial $f$ satisfies $Y - f (X)$ divides $Q (X, Y)$ . Factoring $Q$ gives the list of candidate messages.

The Guruswami-Sudan algorithm improves this by requiring $Q$ to vanish to higher order at each point, which allows decoding more errors at the cost of a larger (but still bounded) list size. The Johnson bound guarantees the list is small.

Visual Beginner

Figure: a plot showing received points $(x_{i}, y_{i})$ as dots in the plane, with two curves passing through most of them. One curve (the true message polynomial) passes through 7 out of 10 points. The other (a spurious curve from the list) passes through 6. The list decoder returns both curves.

Property	Bounded-distance decoding	List decoding
Decoding radius	$⌊(d - 1) /2 ⌋$	Up to $n - nk$ (Johnson bound)
Output	Single codeword or failure	Short list of codewords
Worst-case list size	1	Bounded by Johnson bound
Complexity	$O (n^{2})$ (Berlekamp-Massey)	$O (n^{3})$ (Guruswami-Sudan)

For an RS code with $n = 255, k = 32, d = 224$ : bounded-distance decoding corrects 111 errors; list decoding can correct up to about 191 errors with list size bounded by the Johnson bound.

Worked example Beginner

Consider a toy RS code over a small field. The message is a polynomial $f (X) = a_{0} + a_{1} X$ of degree 1 (so $k = 2$ ). We evaluate at $n = 5$ points $x_{1}, x_{2}, x_{3}, x_{4}, x_{5}$ and receive $y_{1} = f (x_{1}), \dots, y_{5} = f (x_{5})$ .

Suppose 2 errors occur: $y_{3}$ and $y_{5}$ are corrupted. The minimum distance is $d = n - k + 1 = 4$ , so bounded-distance decoding can correct $⌊ 3/2 ⌋ = 1$ error. With 2 errors, it fails.

But list decoding can handle 2 errors. The Sudan algorithm constructs a bivariate polynomial $Q (X, Y)$ of weighted degree that passes through all 5 points. The key constraint: $Q$ has weighted degree small enough that it must factor as $(Y - f (X)) \cdot R (X, Y)$ for at least one valid $f$ . The algorithm finds $Q$ , factors it, and returns the list.

In this case, the list contains two polynomials: the true $f$ and possibly one other. The Johnson bound for $n = 5, d = 4$ gives a list size at most 2, so the output is manageable.

Check your understanding Beginner

Formal definition Intermediate+

Definition (Reed-Solomon code). Let $F_{q}$ be a finite field with $q$ elements, let $n \leq q$ evaluation points $α_{1}, \dots, α_{n} \in F_{q}$ , and let $k \leq n$ . The Reed-Solomon code $RS (n, k)$ is the set of codewords

{(f (α_{1}), f (α_{2}), \dots, f (α_{n})) : f \in F_{q} [X], de g f < k} .

The code has dimension $k$ , length $n$ , and minimum distance $d = n - k + 1$ (the Singleton bound is achieved with equality).

Definition (List decoding). Given a received word $y = (y_{1}, \dots, y_{n}) \in F_{q}^{n}$ and a decoding radius $e$ , a list-decoding algorithm outputs the set

L = {c \in RS (n, k) : d (y, c) \leq e} .

Theorem (Johnson bound). For a code of length $n$ , alphabet size $q$ , and minimum distance $d = n δ$ , the number of codewords within distance $e = n ϵ$ of any received word satisfies

∣ L ∣ \leq \frac{n d ( 1 - d / n )}{n d ( 1 - d / n ) - n e ( 1 - e / n )},

provided $ϵ < J (δ) := \frac{1}{2} (1 - 1 - 2 δ + 2 δ^{2} / q)$ for $q \geq 3$ , or $ϵ < \frac{1}{2} (1 - 1 - 2 δ)$ for $q = 2$ .

For RS codes over large alphabets ( $q \geq n$ ), the Johnson radius simplifies to $J (δ) \approx 1 - 1 - δ$ .

Counterexamples to common slips

The list size is not always 1. For error patterns near the Johnson radius, the list may contain multiple codewords. The algorithm must output all of them.
The Guruswami-Sudan algorithm does not achieve capacity. The Johnson radius $n (1 - 1 - δ)$ is still below the information-theoretic limit $n (1 - H (δ))$ for small $δ$ . Closing this gap requires folden RS codes (Guruswami-Rudra 2008).
The algorithm works over any finite field, but the analysis is cleanest for large fields. Over $F_{2}$ , the situation is more complicated because the alphabet is small.

Key theorem with proof Intermediate+

Theorem (Guruswami-Sudan algorithm). Given an RS code with parameters $(n, k)$ over $F_{q}$ and a received word $y$ , the Guruswami-Sudan algorithm with multiplicity parameter $s$ finds all codewords within distance $e = n - \frac{n}{s + 1} - \frac{k - 1}{s} \cdot s = n - \frac{n + s ( k - 1 )}{s + 1}$ in time polynomial in $n$ and the list size.

Proof sketch. The algorithm has two steps:

Step 1: Interpolation. Find a nonzero bivariate polynomial $Q (X, Y) = \sum_{j} \sum_{i} q_{i, j} X^{i} Y^{j}$ such that:

$Q$ has a zero of multiplicity $s$ at each point $(α_{ℓ}, y_{ℓ})$ , meaning all terms of total degree $< s$ in the Taylor expansion of $Q (α_{ℓ} + a, y_{ℓ} + b)$ vanish.
The $(1, k - 1)$ -weighted degree of $Q$ is at most $D = \frac{s ( n + s ( k - 1 )) - 1}{s + 1}$ (approximately).

The number of coefficients to determine is $(2 D + 2)$ (the number of monomials of weighted degree $\leq D$ ), and the number of constraints from the multiplicity- $s$ condition is $n (2 s + 1) = n s (s + 1) /2$ . For the parameters to be feasible (more variables than equations), we need $(2 D + 2) > n s (s + 1) /2$ , which holds by the choice of $D$ .

Step 2: Factoring. Factor $Q (X, Y)$ into irreducible components over $F_{q} [X, Y]$ . For each irreducible factor of the form $Y - f (X)$ with $de g f < k$ , compute the agreement $∣ {ℓ : f (α_{ℓ}) = y_{ℓ}} ∣$ . Output those $f$ with agreement $\geq n - e$ .

Correctness. If $f$ is a transmitted polynomial with agreement $\geq n - e$ , then $Q (X, f (X))$ has at least $n - e$ roots (counting multiplicity $s$ ) among $α_{1}, \dots, α_{n}$ , contributing at least $s (n - e)$ to the root count. But $de g Q (X, f (X)) \leq D$ by the weighted degree constraint. If $s (n - e) > D$ , then $Q (X, f (X))$ is the zero polynomial, meaning $Y - f (X)$ divides $Q (X, Y)$ . The condition $s (n - e) > D$ holds by the choice of $e$ . $□$

Bridge. The Guruswami-Sudan algorithm builds toward capacity-achieving codes in 46.08.01 where iterative decoding replaces the algebraic approach, and the foundational reason list decoding extends the correction radius is that relaxing the requirement from "unique answer" to "short list of answers" allows the algorithm to push past the half-distance barrier. The central insight is that bivariate polynomial interpolation converts the decoding problem into an algebraic geometry problem, generalises to algebraic-geometry codes via the same interpolation framework, and appears again in 46.07.01 where the weight enumerator provides the algebraic machinery for bounding the list size. The bridge is the weighted degree constraint that couples the interpolation degree to the code parameters, and putting these together the Sudan and Guruswami-Sudan algorithms represent the algebraic approach to decoding at the information-theoretic limit, is dual to the probabilistic approach of iterative decoding.

Exercises Intermediate+

Exercise (hard, short answer).

Prove the Johnson bound for binary codes: for a binary code of length $n$ and minimum distance $d = n δ$ , the number of codewords within Hamming distance $e = n ϵ$ of any received word is at most $\frac{2 e}{2 e - ( n - d )}$ provided $ϵ < (1 - 1 - 2 δ) /2$ .

Hint

Double-count the pairwise distances among codewords in the list. Each pair has distance at least $d$ , and each codeword has distance at most $e$ from the received word.

Answer

Let $L = {c_{1}, \dots, c_{L}}$ be the list of codewords within distance $e$ of $y$ . For each $i$ , let $a_{i} = n - d (y, c_{i}) \geq n - e$ be the agreement. The pairwise distance between $c_{i}$ and $c_{j}$ satisfies:

d (c_{i}, c_{j}) = d (y, c_{i}) + d (y, c_{j}) - 2∣ {t : y_{t} = (c_{i})_{t} = (c_{j})_{t}} ∣

$\leq 2 e - 2∣ {t : y_{t} = (c_{i})_{t} = (c_{j})_{t}} ∣$ .

Since $d (c_{i}, c_{j}) \geq d$ : $d \leq 2 e - 2 \sum_{t} 1 [y_{t} = (c_{i})_{t} = (c_{j})_{t}]$ .

Sum over all pairs: $(2 L) d \leq (2 L) 2 e - 2 \sum_{t} (2 b _{t})$ where $b_{t} = ∣ {i : (c_{i})_{t} = y_{t}} ∣$ .

By Jensen: $\sum_{t} (2 b _{t}) \geq n (2 L ^{2} / n)$ ... Actually, use $\sum b_{t} = \sum a_{i}$ and $\sum b_{t}^{2} \geq (\sum b_{t})^{2} / n$ :

$\sum_{t} (2 b _{t}) = \frac{1}{2} (\sum b_{t}^{2} - \sum b_{t}) \geq \frac{( \sum b _{t} ) ^{2}}{2 n} - \frac{\sum b _{t}}{2} = \frac{( \sum a _{i} ) ^{2}}{2 n} - \frac{\sum a _{i}}{2}$ .

Since $a_{i} \geq n - e$ : $\sum a_{i} \geq L (n - e)$ . Combining and simplifying gives $L \leq \frac{2 n e}{2 n e - n ( n - d )} = \frac{2 e}{2 e - ( n - d )}$ when $2 e > n - d$ .

Exercise (medium, short answer).

Why can the Guruswami-Sudan algorithm not decode beyond the Johnson radius? What happens if the number of errors exceeds the Johnson radius?

Answer

Beyond the Johnson radius, the list size is no longer bounded by a polynomial. There exist received words with exponentially many codewords within distance exceeding the Johnson radius, making it impossible for any polynomial-time algorithm to enumerate the full list. This is not a limitation of the specific algorithm but a combinatorial barrier: the problem of listing all nearby codewords becomes intractable.

To go beyond the Johnson radius, one must use a different code construction (e.g., folded RS codes, concatenated codes) or relax the error model (e.g., probabilistic guarantees rather than worst-case).

Exercise (hard, short answer).

Describe the Sudan algorithm ( $s = 1$ case) in detail. What are the interpolation constraints and the factoring step?

Answer

Sudan algorithm ( $s = 1$ ):

Interpolation: Find a nonzero $Q (X, Y) = \sum_{j = 0}^{⌊ l ⌋} \sum_{i} q_{i, j} X^{i} Y^{j}$ with $(1, k - 1)$ -weighted degree $\leq D = ⌊ 2 nk + k ⌋$ such that $Q (α_{ℓ}, y_{ℓ}) = 0$ for all $ℓ = 1, \dots, n$ .

The number of monomials of weighted degree $\leq D$ is approximately $D^{2} / (2 (k - 1))$ , which exceeds $n$ when $D > 2 n (k - 1)$ . This ensures a nonzero solution exists.

Factoring: Factor $Q (X, Y)$ into irreducible components. For each factor $Y - f (X)$ with $de g f < k$ , check if $f (α_{ℓ}) = y_{ℓ}$ for at least $n - e$ values of $ℓ$ . The decoding radius is $e \leq n - 2 n (k - 1)$ .

Correctness: If $f$ agrees with $y$ in $n - e > 2 n (k - 1)$ positions, then $Q (X, f (X))$ has more than $2 n (k - 1)$ roots but degree at most $D \approx 2 n (k - 1)$ , so $Q (X, f (X)) \equiv 0$ , meaning $Y - f (X) ∣ Q (X, Y)$ .

Lean formalization Intermediate+

Mathlib has Polynomial Fq for univariate polynomials over finite fields and MvPolynomial for multivariate polynomials, but lacks the weighted-degree grading, bivariate interpolation with multiplicities, and the factoring step for bivariate polynomials. A Codex.InformationTheory.ListDecoding module would need to define the weighted-degree monomial count, prove the interpolation feasibility condition, and implement the factoring step. This is a significant formalization effort. This unit ships without a lean_module.

Advanced results Master

Folded Reed-Solomon codes and capacity-achieving list decoding

The Guruswami-Sudan algorithm achieves the Johnson radius but not the information-theoretic limit. Guruswami and Rudra (2008) introduced folded RS codes, where the evaluation points are grouped into windows and the code is defined over a higher alphabet. For folded RS codes of rate $R$ and alphabet size $q^{m}$ for large $m$ , the Guruswami-Sudan algorithm achieves list decoding radius $1 - R - ϵ$ for any $ϵ > 0$ , approaching the Shannon limit $1 - H (R)$ for large alphabets.

The key technique is to increase the alphabet size so that the Johnson radius approaches $1 - R$ , which matches the Singleton bound and hence the information-theoretic limit for large alphabets (where $H (p) \approx p$ ).

Algebraic-geometry codes and list decoding

The Guruswami-Sudan framework extends from RS codes (evaluation of polynomials at points) to algebraic-geometry codes (evaluation of functions at points on an algebraic curve). The interpolation polynomial $Q (X, Y)$ becomes a polynomial in the function field of the curve, and the factoring step uses the Riemann-Roch theorem to bound the number of candidate functions.

For AG codes over the Garcia-Stichtenoth tower of function fields, the Guruswami-Sudan algorithm achieves list-decodable capacity for any rate $R$ over a fixed alphabet, matching the Zyablov bound and approaching the Shannon limit as the field size grows.

The Parvaresh-Vardy and Guruswami-Rudra constructions

Parvaresh and Vardy (2005) introduced a novel code construction where each codeword encodes not just one polynomial $f$ but a correlated tuple $(f, f^{d} mod E (X))$ for an irreducible $E$ . This correlation structure allows the decoding algorithm to extract more information from each received symbol, pushing the decoding radius beyond the Johnson bound for the original RS code.

Guruswami and Rudra (2008) combined the Parvaresh-Vardy idea with code folding to achieve list-decoding capacity. The resulting codes are explicit, polynomial-time constructible, and list-decodable up to radius $1 - R - ϵ$ for any rate $R$ and $ϵ > 0$ , over an alphabet whose size depends polynomially on $1/ ϵ$ .

Synthesis. List decoding pushes the correction capability of algebraic codes from the half-distance barrier to the Johnson radius, and folded constructions push further to the information-theoretic limit. The central insight is that relaxing unique decoding to list decoding converts an algebraic bottleneck (the interpolation degree) into a combinatorial one (the list size), and the Johnson bound guarantees the list is small. The foundational reason the Guruswami-Sudan algorithm works is that bivariate interpolation with multiplicities extracts maximal information from the received word, generalises from RS codes to AG codes via function field evaluation, and appears again in 46.08.01 where iterative decoding provides the probabilistic counterpart. The bridge is the interpolation framework: a polynomial that vanishes at all received points must also vanish along every nearby codeword, and putting these together the algebraic and probabilistic approaches converge on the Shannon limit.

Full proof set Master

Proposition (List size bound for RS codes). For an RS code of length $n$ and dimension $k$ over $F_{q}$ with $q \geq n$ , the number of codewords within distance $e$ of any received word is at most $⌊ n / (n - 2 e) ⌋ \cdot k$ when $e < n /2$ .

Proof. Let $f_{1}, \dots, f_{L}$ be the polynomials whose codewords are within distance $e$ of $y$ . For each $f_{i}$ , let $S_{i} = {ℓ : f_{i} (α_{ℓ}) = y_{ℓ}}$ be the agreement set, with $∣ S_{i} ∣ \geq n - e$ .

For any two distinct polynomials $f_{i}, f_{j}$ of degree $< k$ : they agree on at most $k - 1$ evaluation points, so $∣ S_{i} \cap S_{j} ∣ \leq k - 1$ .

By inclusion-exclusion: $n - e \leq ∣ S_{i} ∣ \leq ∣ S_{1} \cup \dots \cup S_{L} ∣/ L + (L - 1) (k - 1) / L$ ... A cleaner argument uses the second moment method.

$\sum_{i \neq = j} ∣ S_{i} \cap S_{j} ∣ \leq (2 L) (k - 1)$ and $\sum_{i} ∣ S_{i} ∣ \geq L (n - e)$ .

Since $\sum_{ℓ} ∣ {i : ℓ \in S_{i}} ∣^{2} = \sum_{i} ∣ S_{i} ∣ + 2 \sum_{i < j} ∣ S_{i} \cap S_{j} ∣ \leq L (n - e) + L (L - 1) (k - 1)$ , and by Cauchy-Schwarz, $\sum_{ℓ} ∣ {i : ℓ \in S_{i}} ∣^{2} \geq (\sum_{ℓ} ∣ {i : ℓ \in S_{i}} ∣)^{2} / n = (\sum_{i} ∣ S_{i} ∣)^{2} / n \geq L^{2} (n - e)^{2} / n$ .

Combining: $L^{2} (n - e)^{2} / n \leq L (n - e) + L (L - 1) (k - 1)$ , giving $L (n - e)^{2} / n \leq (n - e) + (L - 1) (k - 1)$ . For $L$ large relative to $k$ , this gives $L \leq O (n (k - 1) / (n - 2 e)^{2})$ . $□$

Connections Master

40.06.08 — Cyclic codes, BCH codes, and Reed-Solomon codes; the evaluation-code formulation is the starting point for list decoding.
46.07.01 — Weight enumerators and the MacWilliams identity; the distance distribution governs the list size via the Johnson bound.
46.08.01 — LDPC codes and iterative decoding provide the probabilistic counterpart to algebraic list decoding.
46.03.04 — The BSC and BEC capacity formulas define the information-theoretic limits that list decoding approaches.
46.03.03 — Fano's inequality and the channel coding converse establish the limits that list decoding aims to reach.

Historical & philosophical context Master

Madhu Sudan introduced the list-decoding algorithm for Reed-Solomon codes in his 1997 paper "Decoding of Reed-Solomon Codes Beyond the Error-Correction Bound" (Journal of Complexity 13(1), pp. 180-193). Sudan's insight was to use bivariate polynomial interpolation rather than the univariate approach of the Berlekamp-Massey algorithm, converting the decoding problem from a root-finding problem to a polynomial-factoring problem.

Venkatesan Guruswami and Madhu Sudan improved the algorithm in their 1999 paper "Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes" (IEEE Trans. Info. Theory 45(6), pp. 1757-1767), introducing the multiplicity parameter that pushes the decoding radius to the Johnson bound. This paper won the IEEE Information Theory Society Paper Award.

The Johnson bound dates to Selmer Johnson's 1962 paper "A New Upper Bound for Error-Correcting Codes" (IRE Trans. IT-8, pp. 203-207). Johnson was studying the combinatorial structure of error-correcting codes and derived the bound using double-counting of pairwise distances, a technique that prefigured the modern analysis of list decodability.

Guruswami and Rudra's 2008 result on folded RS codes achieving list-decoding capacity ("Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy," STOC 2008) resolved a major open problem by providing explicit, polynomial-time decodable codes that achieve the Shannon limit for any rate over sufficiently large alphabets.

Bibliography Master

@article{sudan1997,
  author  = {Sudan, M.},
  title   = {Decoding of {Reed-Solomon} Codes Beyond the Error-Correction Bound},
  journal = {Journal of Complexity},
  volume  = {13},
  number  = {1},
  pages   = {180--193},
  year    = {1997},
}
@article{guruswami-sudan1999,
  author  = {Guruswami, V. and Sudan, M.},
  title   = {Improved Decoding of {Reed-Solomon} and Algebraic-Geometry Codes},
  journal = {IEEE Transactions on Information Theory},
  volume  = {45},
  number  = {6},
  pages   = {1757--1767},
  year    = {1999},
}
@article{johnson1962,
  author  = {Johnson, S. M.},
  title   = {A New Upper Bound for Error-Correcting Codes},
  journal = {IRE Transactions on Information Theory},
  volume  = {IT-8},
  pages   = {203--207},
  year    = {1962},
}
@book{macwilliams-sloane1977,
  author    = {MacWilliams, F. J. and Sloane, N. J. A.},
  title     = {The Theory of Error-Correcting Codes},
  publisher = {North-Holland},
  year      = {1977},
}
@inproceedings{guruswami-rudra2008,
  author    = {Guruswami, V. and Rudra, A.},
  title     = {Explicit Codes Achieving List Decoding Capacity: Error-Correction with Optimal Redundancy},
  booktitle = {Proceedings of STOC},
  year      = {2008},
}

Prerequisites

46.07.01
40.06.08

Tier anchors

beginner: MacWilliams & Sloane 1977 The Theory of Error-Correcting Codes (North-Holland) Ch. 12 and Guruswami-Sudan survey (the puzzle of decoding beyond half the distance, why a list of answers helps)
intermediate: Guruswami & Sudan 1999 Improved decoding of Reed-Solomon and algebraic-geometry codes IEEE Trans. Info. Theory 45(6) 1757-1767; Sudan 1997 Decoding of Reed-Solomon codes beyond the error-correction bound
master: Guruswami & Sudan 1999; Sudan 1997; Guruswami, Rudra & Sudan 2002 Essential coding theory Ch. 6-7; Johnson 1962 A new upper bound for error-correcting codes IRE Trans. IT-8 203-207

References

MacWilliams, F. J. & Sloane, N. J. A. — The Theory of Error-Correcting Codes · North-Holland (1977). Chapter 12: Reed-Solomon codes as evaluation codes over finite fields, their minimum distance properties ( $d = n - k + 1$ ), and the Berlekamp-Massey decoding algorithm for bounded-distance decoding up to $⌊(d - 1) /2 ⌋$ errors. The chapter also covers BCH codes as subfield subcodes of RS codes and the relation to cyclic codes.
Sudan, M. — Decoding of Reed-Solomon Codes Beyond the Error-Correction Bound · Journal of Complexity 13(1) (1997) 180-193. Introduces the list-decoding algorithm for RS codes based on bivariate polynomial interpolation. Given $n$ point-value pairs $(x_{i}, y_{i})$ , the algorithm finds a bivariate polynomial $Q (X, Y)$ of weighted degree satisfying a zero-multiplicity condition, then factors $Q$ to recover all polynomials $f$ of degree $< k$ with $f (x_{i}) = y_{i}$ for at least $n - e$ points. Achieves decoding radius $e = n - 2 nk$ for list size $O (n)$ .
Guruswami, V. & Sudan, M. — Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes · IEEE Transactions on Information Theory 45(6) (1999) 1757-1767. Improves Sudan's algorithm by introducing multiplicities in the interpolation step. The key insight: requiring $Q (X, Y)$ to vanish to order $s$ at each received point allows decoding up to $e = n - n (n - L)$ where $L$ is the list size. For $L = k - 1$ , this achieves $e = n (1 - 1 - d / n)$ , reaching the Johnson bound.
Johnson, S. M. — A New Upper Bound for Error-Correcting Codes · IRE Transactions on Information Theory IT-8 (1962) 203-207. The Johnson bound: for a code of length $n$ and minimum distance $d = n δ$ , the number of codewords within distance $e = n ϵ$ of any received word is at most $\frac{n δ ( 1 - δ )}{n δ ( 1 - δ ) - n e ( 1 - ϵ )}$ when $ϵ < \frac{1}{2} (1 - 1 - δ)$ . This bound governs the list size in list decoding.

Estimated time

beginner: 20m
intermediate: 50m
master: 100m