List Decoding

Every time data travels — through a satellite link, a scratched CD, a cellular tower — some bits arrive wrong. Error-correcting codes are the invisible shield that repairs the damage: they add carefully chosen redundancy so a decoder can recover the original message even when the channel flips some symbols.

The classical recipe, called unique decoding, works beautifully as long as the number of corrupted symbols stays below half the minimum distance $d$ of the code. Cross that threshold and two codewords become equally plausible; the decoder is stuck.

In 1997, Madhu Sudan broke that wall. He showed that, instead of demanding a unique answer, you can ask for a short list of all codewords within a larger radius. Venkatesan Guruswami and Sudan refined the idea in 1998 into the celebrated Guruswami-Sudan algorithm, which efficiently list-decodes Reed-Solomon codes up to the Johnson bound — far beyond $d/2$. The result earned Guruswami the 2002 Packard Fellowship and reshaped coding theory permanently.

The demo below works with a tiny Reed-Solomon-like code over the alphabet $\{0,1,\dots,6\}$. Each codeword is a degree-1 polynomial $f(x) = ax + b$ evaluated at positions $0,1,2,3,4,5,6$ — so each codeword has length 7 and minimum distance 6.

Use the sliders to inject errors into a received word, then click Unique decode or List decode to see which candidates survive.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="panel">
  <div class="row">
    <span class="label">{{label_a}}</span>
    <input type="range" id="sliderA" min="0" max="6" value="2" class="slider">
    <span id="valA" class="val">2</span>
  </div>
  <div class="row">
    <span class="label">{{label_b}}</span>
    <input type="range" id="sliderB" min="0" max="6" value="1" class="slider">
    <span id="valB" class="val">1</span>
  </div>
</div>
<div class="panel">
  <div class="row">
    <span class="label">{{label_errors}}</span>
    <input type="range" id="sliderE" min="0" max="5" value="2" class="slider">
    <span id="valE" class="val">2</span>
  </div>
</div>
<div id="codeword-row" class="coderow"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btnUnique" type="button">{{btn_unique}}</button>
  <button id="btnList" type="button">{{btn_list}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="result" class="result"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.panel { background: #f4f7fa; border: 1px solid #dde3ea; border-radius: 8px; padding: .6rem .8rem; margin-bottom: .5rem; }
.row { display: flex; align-items: center; gap: .6rem; margin: .2rem 0; }
.label { font-size: .83rem; color: #555; min-width: 80px; }
.slider { flex: 1; accent-color: #1d3557; }
.val { font: 700 .9rem ui-monospace, monospace; color: #1d3557; min-width: 18px; }
.coderow { display: flex; gap: 4px; margin: .5rem 0; flex-wrap: wrap; }
.sym { width: 36px; height: 36px; display: flex; align-items: center; justify-content: center;
       font: 700 15px ui-monospace, monospace; border-radius: 6px; }
.sym.clean { background: #d4edda; color: #155724; border: 1px solid #b1dfbb; }
.sym.corrupt { background: #f8d7da; color: #721c24; border: 1px solid #f5c6cb; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: .85rem; line-height: 1.6; }
.result b { color: #1d3557; }
.candidate { background: #eef2f7; border-radius: 6px; padding: .2rem .5rem; display: inline-block; margin: .15rem .1rem;
             font: 600 .82rem ui-monospace, monospace; }
.candidate.match { background: #d4edda; color: #155724; }

// Code not found

Notice the transition: unique decoding succeeds only when errors $\leq 2$ (half of $d=6$ rounds down to 2). List decoding keeps finding candidates even with 3 or 4 errors, returning a small list instead of giving up. Checking every candidate is fast; the power of list decoding is that the list stays polynomial in size even past the unique-decoding radius.

How hard is list decoding? Surprisingly tractable — and here is why.

The half-distance wall. A code with minimum distance $d$ can uniquely correct up to $\lfloor (d-1)/2 \rfloor$ errors. Beyond that, a received word may be equidistant from two codewords, and any decoder must guess.

The list-decoding insight. Instead of requiring a unique answer, return every codeword within Hamming distance $\rho$ of the received word. As long as $\rho$ stays below the Johnson bound $n - \sqrt{n(n-d)}$, the list size is guaranteed polynomial — there can be at most $O(n^2)$ codewords that close together.

Guruswami-Sudan (1998). The algorithm for Reed-Solomon codes works in two algebraic steps:

1. Interpolation: find a bivariate polynomial $Q(x, y)$ of low degree that passes through all $(x_i, y_i)$ pairs, where $y_i$ is the received symbol at position $x_i$.
2. Factorization: extract every linear factor $y - f(x)$ of $Q$; each factor corresponds to one candidate codeword.

Both steps run in polynomial time $O(n^3)$, and the list has size $O(n)$. This is a sharp contrast with brute-force search over $q^n$ codewords.

Open questions. Achieving the Singleton bound (decoding up to $n - k$ errors, the information-theoretic limit) in polynomial time is still open for large alphabets. For binary codes, the situation is even harder: list decoding up to the Zyablov bound efficiently is an active frontier, and whether one can reach capacity with linear-time algorithms touches the deep theory of expander codes and pseudorandomness.

List decoding is not just theory — it shapes systems you rely on every day:

• Storage and optical media. Reed-Solomon codes protect hard drives, DVDs and QR codes. Burst errors from a scratch can exceed the unique-decoding radius; list decoding recovers the data by returning candidates and disambiguating with a tiny checksum.
• Deep-space communication. NASA's Voyager and Cassini missions used concatenated codes where list decoding of the outer Reed-Solomon layer handles the large error bursts that unique decoding cannot.
• Pseudorandomness and complexity theory. List-decodable codes are the key ingredient in hardness amplification: if a Boolean function is hard on average, you can use a list-decodable code to turn it into one that is worst-case hard — the foundation of derandomization and of connections between learning with errors and cryptography.
• Streaming and network codes. In network coding over lossy links, list decoding tolerates packet erasures that push past the unique-decoding threshold.

The thread tying them together: whenever errors are so heavy that a unique answer is untenable, a short list of candidates is worth more than silence.

Unique decoding draws a sharp line at half the minimum distance and refuses to cross it. List decoding erases that line — not by working harder, but by reframing the question. Ask for all plausible answers instead of the answer, and suddenly polynomial-time algorithms reach correction radii that were thought impossible.

The Guruswami-Sudan algorithm turns that insight into algebra: interpolate a bivariate polynomial, factor it, collect the candidates. It runs fast, the list stays small, and it has reshaped not just coding theory but the foundations of pseudorandomness and complexity — a reminder that sometimes the right move is to widen the question rather than sharpen the answer. For a deeper look at the limits of computation that list decoding touches, see P vs NP.