Reed-Muller codes and the gap to capacity
Reaching capacity was the breakthrough; reaching it fast is the open question
Motivation
A code achieves capacity if its rate can be pushed arbitrarily close to the channel’s theoretical maximum while decoding still succeeds. That is an asymptotic statement, and asymptotic statements have a hidden parameter: how fast. The scaling exponent measures it — how quickly the gap to capacity closes as the blocklength grows — and it is what decides whether a code is usable at finite lengths or only in the limit.
For random codes the answer is easy and good: the gap closes like the inverse square root of the blocklength. For explicit codes with efficient decoders it is much harder, and the difference is not academic. Polar codes were known to achieve capacity years before they were known to efficiently achieve it, and closing that gap was a separate line of work.
Reed-Muller codes are in the earlier state. They achieve capacity on the binary erasure channel — proved only in 2016, and regarded as a breakthrough — and nothing is known about the rate.
Provenance and history
Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke proved that Reed-Muller codes achieve capacity over the BEC, recovering from erasure rate \(\varepsilon - o_M(1)\) where \(\varepsilon = 1 - \mathrm{Rate}\). Their argument runs through symmetry and sharp-threshold machinery, which by its nature establishes that a threshold exists without bounding the width of the window around it.
Jarosław Błasiok, Paul Lou, Alon Rosen and Madhu Sudan, Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR (IACR ePrint 2026/664), need the rate and give the question a new consequence. Their subject is the widely-held conjecture, going back to Alekhnovich and reiterated by Barak, that expansion of the constraint graph implies hardness of noisy \(k\)-XOR — a conjecture backed by lower bounds in restricted models such as Sum-of-Squares and low-degree polynomials, which are closely tied to expansion.
They refute it. Their key insight is that by an appropriate interpretation of the vertices, the noisy XOR problem on a coset graph becomes the problem of decoding Reed-Muller codes from random errors. Combining that with the lossless expanders of Guruswami, Umans and Vadhan — which they show can be read as coset graphs — gives explicit graphs with near-optimal expansion on which noisy \(k\)-XOR is solvable in polynomial time.
The unconditional version of that refutation has \(M = 2^{\Theta(\log^2 N)}\) constraints, quasi-polynomially many in the number of variables. Getting to polynomially many needs the rate of convergence: “To get a result for a polynomial number of equations in the number of variables we need much faster rate of convergence to capacity than is currently known.” Hence their Conjecture 14, and the weaker Conjecture 16 that already suffices.
The question is not theirs. They record that gap-to-capacity for Reed-Muller codes on symmetric channels “has been explicitly raised in [AY19, Section V], [Has+18; MHU14], and in [ASY21]”.
Parameter lattice
Gap-to-capacity, by code family.
| Family | Capacity | Gap to capacity |
|---|---|---|
| Random codes | yes | scaling exponent \(1/\gamma = 2\); simple |
| Polar codes | yes | efficiently achieved for BSC; variants reach \(1/\gamma \to 2\) |
| Reed-Muller | yes, Kudekar et al. 2016 | c/0097 — open |
What each conjecture gives the noisy \(k\)-XOR refutation.
| Assumption | Constraints \(M\) | Noise rate \(\eta\) | Status |
|---|---|---|---|
| none | \(2^{\Theta(\log^2 N)}\) | \(1/3\), constant | proved, Main Theorem 1 |
| Conjecture 16 (weak erasure recovery) | \(N^{\Theta(1)}\) | \(N^{-c}\), any \(c>0\) | conditional, Main Theorem 2 |
| Conjecture 14 (efficient capacity) | — | — | implies Conjecture 16 |
Both conditional rows are c/0097. Note the direction: the refutation of the expansion conjecture stands unconditionally; only its strongest parameter setting needs the coding-theory input.
The equivalent algebraic form
Worth stating separately, because it strips the problem to combinatorics. Let \(\mathbb{F}_2[X]_{\le r}\) have dimension \((1-\varepsilon)M\), and let \(S\) be a random subset of \((1-\varepsilon)M + M^{1-\gamma}\) points of the hypercube \(\mathbb{F}_2^m\). Conjecture 14 holds if and only if, with probability \(1-o(1)\), no non-zero polynomial in \(\mathbb{F}_2[X]_{\le r}\) vanishes on all of \(S\). The excess over the dimension is only \(M^{1-\gamma}\) points, and the claim is that this already forces the zero polynomial.