Expander Codes

Every time you stream a video, send a message, or store a file, the data crosses a channel that can flip bits at random. Error-correcting codes add carefully chosen redundancy so that the receiver can recover the original message despite the noise. The question is: how fast can you do that recovery?

Classical codes such as Reed-Solomon are excellent but their decoders run in $O(n \log n)$ or $O(n^{2})$ time. For a long time it was an open problem whether codes with constant rate and constant relative distance — properties needed for them to be practically useful — could also be decoded in linear time $O(n)$.

In 1996, Michael Sipser and Daniel Spielman answered the question with a surprise: build your code on top of an expander graph — a sparse graph where every small set of vertices has many neighbors outside it — and a simple greedy decoder called bit-flipping runs in $O(n)$ time and corrects a constant fraction of errors. The key insight is purely graph-theoretic: expansion forces every corrupted bit to be the minority vote in many of its check equations, making it easy to identify and correct it.

Today expander codes are a cornerstone of modern coding theory, with relatives powering every LDPC-based standard from Wi-Fi to 5G.

The demo below shows a small expander-code codeword (8 bits). Each bit on the left is connected to two check nodes on the right. A check node is satisfied when the XOR (parity) of its connected bits is zero; otherwise it is unsatisfied (shown in red).

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="layout">
  <div class="col" id="bit-col"><!-- {{c_bits_col}} --></div>
  <svg id="edges-svg" class="edges-svg" aria-hidden="true"></svg>
  <div class="col" id="check-col"><!-- {{c_checks_col}} --></div>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="corrupt" type="button">{{btn_corrupt}}</button>
  <button id="decode" type="button">{{btn_decode}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend">
  <span class="legend-ok">&#x25CF; {{legend_ok}}</span>
  <span class="legend-err">&#x25CF; {{legend_err}}</span>
  <span class="legend-flip">&#x25CF; {{legend_flip}}</span>
</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 .8rem; line-height: 1.5; }
.layout { display: flex; align-items: center; gap: 0; min-height: 320px; position: relative; }
.col { display: flex; flex-direction: column; gap: 6px; z-index: 1; }
#bit-col { margin-right: 6px; }
#check-col { margin-left: 6px; }
.edges-svg { flex: 1; height: 320px; overflow: visible; }
.node { width: 40px; height: 40px; display: flex; align-items: center;
        justify-content: center; font: 700 14px ui-monospace, monospace;
        border: 2px solid #adb1b8; background: #e0e4ea;
        transition: background .25s, border-color .25s; user-select: none; }
.bit-node { border-radius: 50%; }
.check-node { border-radius: 6px; }
.corrupted { background: #e63946; border-color: #c92f3c; color: #fff; }
.flipped-now { background: #ff9f1c; border-color: #e0890f; color: #fff; }
.check-ok { background: #d4edda; border-color: #74c489; color: #0a7d33; font-size: 18px; }
.check-fail { background: #f8d7da; border-color: #e63946; color: #c92f3c; font-size: 18px; }
.edge { stroke: #c8cdd6; stroke-width: 1.4; transition: stroke .25s; }
.edge.active { stroke: #e63946; stroke-width: 2.2; }
.edge.flipping { stroke: #ff9f1c; stroke-width: 2.2; }
.status { font-size: .92rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.legend { display: flex; gap: 1rem; font-size: .78rem; color: #555; flex-wrap: wrap; }
.legend-ok { color: #0a7d33; }
.legend-err { color: #c92f3c; }
.legend-flip { color: #e0890f; }

// Code not found

Click Corrupt to flip a few bits at random, then click Decode (bit-flip) to run the Sipser-Spielman decoder. On each step, any bit that is the minority in more than half its check equations gets flipped. Watch how the decoder homes in on the errors — and notice that it always terminates in a small number of rounds, independent of the codeword length.

What makes expander codes remarkable is that they achieve three goals simultaneously that were previously thought to require trade-offs:

• Constant rate. The ratio of message length to codeword length is bounded away from zero: $k/n \geq R_{0} > 0$. You never drown the message in redundancy.
• Constant relative distance. Any two distinct codewords differ in at least a constant fraction $\delta_{0} \cdot n$ of positions, so the code tolerates a constant fraction of errors.
• Linear-time decoding. The Sipser-Spielman bit-flipping algorithm runs in $O(n)$ time. The decoder loops: for each bit, count how many of its check equations are unsatisfied; if more than half are unsatisfied, flip the bit. Repeat until all checks pass.

Why does this work? The expansion property guarantees that the set of corrupted bits has many unsatisfied checks, and that each corrupted bit is incident to more unsatisfied checks than satisfied ones — making it the clear flip candidate. A classical result shows that $O(n)$ rounds suffice and each round takes $O(n)$ time.

The construction uses a $(n, d, \lambda)$-expander: a $d$-regular bipartite graph on $n$ left vertices and $m$ right vertices where the second eigenvalue $\lambda$ of the adjacency matrix is much smaller than $d$. The spectral gap $d - \lambda$ controls expansion: the larger it is, the more aggressively small sets expand into new neighbors, and the more errors the code can correct.

Sipser and Spielman's proof was a landmark because it separated three concerns that classical algebraic codes bundled together: structure (the graph), redundancy (the rate), and noise tolerance (the distance). Expander codes showed these could all be controlled independently by choosing the right graph — a purely combinatorial insight transplanted into information theory. See also information-theoretic limits of compression for how rate constraints arise more broadly.

Expander codes are the theoretical foundation for the most widely deployed error-correcting codes in existence:

• Wi-Fi (802.11n/ac/ax): uses LDPC codes — Low-Density Parity-Check codes — which are the modern cousin of expander codes. The same sparse bipartite graph structure, the same iterative decoder, the same linear-time behavior.
• 5G NR: the data channel uses LDPC codes for exactly the same reasons. Decoding a 5G frame is an expander-code bit-flip decoder at scale, running in hardware at gigabit speeds.
• Satellite and deep-space links: NASA's Consultative Committee for Space Data Systems mandates LDPC codes for missions that cannot afford retransmission — the data either arrives corrected or is lost forever.
• Solid-state drives and NAND flash: as flash cells wear out, the raw error rate grows; LDPC decoders running in $O(n)$ time on dedicated silicon keep the logical bit-error rate below $10^{-15}$.
• Theoretical computer science: expander graphs — the combinatorial object at the heart of expander codes — appear in derandomization, hardness amplification, and the construction of pseudorandom generators. Understanding expansion means understanding much of modern complexity theory.

The story of expander codes is a textbook case of how a single mathematical idea — the expansion property of graphs — can simultaneously solve an open problem in information theory and provide the engineering blueprint for a generation of communication standards.

Expander codes tell a clean story: pick a graph with the right expansion properties, define your code using its parity checks, and a childishly simple decoder — just flip whichever bit loses the majority vote — will fix all the errors in linear time.

The depth lies in the guarantee. Expansion forces every small set of errors to be a minority in its own neighborhood, making each corrupt bit self-identifying. Sipser and Spielman turned that geometric intuition into a proof, and engineers turned that proof into hardware that ships in every smartphone today.

If you want to go deeper, expander codes are the entry point to the vast world of graph-based codes and to the role expander graphs play across all of theoretical computer science — from derandomization to the P vs NP problem itself.