🔢 mathematics

Time- and Space-Efficient List Decoding up to Capacity

This paper presents a construction of list-decodable codes that achieve capacity with deterministic time and space complexity of $N^{1+\tau}$ and $N^{\tau}$ respectively, while maintaining a constant output list size and alphabet size.

Original authors: Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters

Published 2026-08-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, information is fragile. When data travels across networks or sits on a hard drive, it is constantly threatened by noise, interference, and corruption. A single flipped bit can turn a clear image into static or a correct bank transfer into a lost sum. To combat this, engineers use error-correcting codes, which are essentially mathematical recipes that add extra, redundant information to a message before it is sent. This redundancy acts like a safety net, allowing a receiver to reconstruct the original message even if parts of it arrive damaged. For decades, the goal has been to make these safety nets as efficient as possible: adding the least amount of extra data while still being able to fix the most errors. The theoretical limit of this efficiency is known as "capacity." Reaching capacity means a code is performing as well as physics and mathematics allow, correcting the maximum number of errors for a given amount of extra data.

However, there is a second, often overlooked challenge in this field: the physical resources required to run the decoding process. While modern computers are incredibly fast, they are also limited by how much memory they can hold at once. Some of the most powerful decoding methods found in recent years are incredibly fast but require massive amounts of memory to operate, making them impractical for devices with tight constraints, such as satellites, sensors, or secure hardware. Furthermore, many of these efficient methods rely on randomness—using a coin flip or a random seed to guide the decoding process. While randomness works well in theory, it can be a liability in real-world systems where predictability and security are paramount. A deterministic algorithm, one that follows a strict, unchanging path without random choices, is far more desirable for building reliable, secure, and reproducible systems.

A team of researchers has now bridged the gap between these competing demands. They have constructed a new family of error-correcting codes that achieve the theoretical maximum efficiency while being decoded by an algorithm that is both deterministic and incredibly frugal with memory. Their work proves that it is possible to correct nearly the maximum number of errors a code can handle without needing vast amounts of memory or relying on random chance. The algorithm they developed runs in time that is almost linear with the size of the data, meaning it scales efficiently, but it uses a tiny fraction of the memory that previous high-performance methods required. This is a significant shift, as it demonstrates that high performance does not have to come at the cost of memory or determinism.

The core of their achievement lies in a clever reimagining of how decoding works. Traditionally, decoding a corrupted message involves looking at the entire message at once to find the original. This global view is powerful but memory-intensive. Alternatively, "local" decoding looks at only a tiny piece of the message at a time, which is memory-efficient but usually requires randomness to work correctly. The researchers realized that by allowing a small, efficient pre-processing step that happens before the actual decoding begins, they could make the local process deterministic. Think of this pre-processing as a one-time setup where the decoder prepares a map of the terrain; once the map is ready, the actual journey of decoding can proceed step-by-step with perfect certainty and minimal memory, without needing to look at the whole picture again.

To build this system, the researchers used a structure known as a tensor code, which can be visualized as a multi-dimensional grid of data where every row and every column must follow specific rules. They developed a new method to navigate this grid. Instead of trying to decode the entire grid at once, their algorithm breaks the problem down into smaller, manageable pieces. It uses a technique to select a few representative columns from the grid, decodes those, and then uses that information to infer the rest. Crucially, they devised a way to verify the correctness of these inferences without storing the entire grid in memory. They created a series of tests that act like a quality control check, ensuring that the decoded pieces fit together correctly and match the received data, all while using very little space.

The result is a system that is both powerful and practical. The codes they constructed can correct errors up to the theoretical limit, known as capacity, for any desired rate of data transmission. The decoding algorithm runs in time that is nearly proportional to the length of the message, making it fast enough for real-time applications. Most importantly, it uses memory that grows very slowly with the message size, meaning it can handle massive amounts of data without running out of space. This is a departure from previous methods that either sacrificed speed for memory, used randomness, or failed to reach the theoretical limits of efficiency. By combining a high-rate base code with a new type of deterministic local decoding, the researchers have shown that the trade-offs between speed, memory, and reliability can be overcome.

This work also addresses a fundamental question in computer science: how much randomness is truly necessary for efficient computation? For a long time, it was believed that certain types of local decoding simply could not be deterministic. The researchers showed that this belief was based on a specific definition of locality that did not account for a small, efficient pre-processing step. By relaxing this definition slightly, they unlocked the ability to create deterministic algorithms that are just as powerful as their randomized counterparts. This insight opens the door for future applications in cryptography and secure communications, where deterministic behavior is often a strict requirement. The ability to decode data with certainty, using minimal resources, and without random seeds, provides a new foundation for building robust digital systems.

The implications of this discovery extend beyond just fixing corrupted files. The techniques used to construct these codes, such as the specific way they combine different types of codes and the methods they use to prune incorrect possibilities, are general tools that can be applied to other problems in coding theory. The researchers demonstrated that their approach works not just for simple error correction but also for a more complex task called list recovery, where the goal is to find all possible original messages that could have resulted in a corrupted signal. This versatility suggests that the underlying principles they uncovered are robust and widely applicable.

In the broader context of computing, this work represents a step toward more efficient and reliable digital infrastructure. As data volumes continue to explode, the need for algorithms that can process information quickly without overwhelming memory becomes increasingly critical. The ability to achieve the best possible error correction while staying within tight memory constraints means that future devices can be smaller, more secure, and more capable. The researchers have provided a blueprint for how to build these systems, proving that the theoretical limits of efficiency are not just mathematical abstractions but achievable realities in the physical world of computing. Their success in creating a deterministic, space-efficient decoder that reaches capacity marks a significant milestone in the ongoing effort to make digital communication more resilient and efficient.

=== SUMMARY ===

Technical Summary: Time- and Space-Efficient List Decoding up to Capacity

Problem Statement

The paper addresses the construction of error-correcting codes that achieve the optimal trade-off between rate ( $R$ ) and list-decoding radius ( $\rho$ ), known as capacity. Specifically, the authors seek codes that are list-decodable up to radius $\rho \approx 1 - R$ with a constant list size, while simultaneously satisfying two stringent efficiency constraints:

Time Efficiency: The decoding algorithm must run in near-linear time ( $N^{1+\tau}$ for arbitrarily small $\tau > 0$ ).
Space Efficiency: The decoding algorithm must use sublinear space ( $N^\tau$ ).

While prior work had achieved capacity-achieving list-decoding with near-linear time, these algorithms were either randomized or required linear space. Conversely, recent deterministic low-space algorithms (e.g., Cook and Moshkovitz [CM26]) achieved sublinear space but fell far short of capacity, operating at very low rates. The central challenge is to construct deterministic algorithms that are both time- and space-efficient while approaching capacity.

Methodology and Technical Approach

The authors' approach centers on the construction of Deterministic Locally List-Recoverable Codes (DLLRCs). They observe that while purely local deterministic list-decoding is impossible (as an adversary could corrupt the few coordinates a local algorithm queries), a "deterministic local" notion becomes feasible if the algorithm is allowed a small amount of global pre-processing (sublinear space and near-linear time) before the local queries begin.

The construction proceeds in three main stages:

1. Deterministic Approximate Local List-Recovery (DALLRC) via Tensor Codes

The core technical engine is a deterministic version of the randomized local list-recovery algorithm for tensor codes, originally developed by Haeupler, Reich, and Wootters [HRW19].

Tensor Codes: The authors construct codes $C^{\otimes t}$ (tensor products of a base code $C$ ).
Derandomization: They derandomize the selection of columns used in the recursive decoding process by iterating over all seeds of a sampler (a pseudorandom object).
Pruning Spurious Candidates: A straightforward derandomization would cause the list of candidate local algorithms to grow exponentially. To maintain a constant list size, the authors introduce a suite of three low-space deterministic testers ( $Test_1, Test_2, Test_3$ $T es t_{1}, T es t_{2}, T es t_{3}$ ) that prune the list during pre-processing:
- $Test_1$ : Verifies the candidate string is close to the code $C^{\otimes t}$ .
- $Test_2$ : Verifies the candidate string is close to the input lists $S$ .
- $Test_3$ : Ensures the candidate is distinct from previously accepted candidates.
Approximation: The resulting algorithm is an Approximate DLLRC (DALLRC), meaning it recovers codewords correctly on a $1-\epsilon$ fraction of coordinates, rather than 100%.

2. From Approximate to Exact: Intersection with DLCC

To remove the approximation error ( $\epsilon$ ) and achieve exact recovery, the authors intersect the high-rate DALLRC with a Deterministic Locally Correctable Code (DLCC).

They utilize a high-rate DLCC construction based on Lifted Reed-Solomon codes, adapting results from Cook and Moshkovitz [CM25].
By intersecting the DALLRC (which handles the bulk of the list-recovery) with the DLCC (which corrects the remaining $\epsilon$ fraction of errors), they obtain a high-rate exact DLLRC.

3. Capacity Achievement via AEL Distance Amplification

The high-rate DLLRC constructed above still has a decoding radius smaller than the capacity limit. To reach capacity, the authors apply the Alon-Edmonds-Luby (AEL) distance amplification transformation.

This transformation, based on bipartite expander graphs, boosts the decoding radius of a high-rate code to approach $1-R$ .
Crucially, the authors prove that the AEL transformation preserves the deterministic, low-space, and near-linear-time properties of the underlying DLLRC.

Key Contributions and Results

The paper presents the following main results:

Main Theorem (Theorem 1.2 / Corollary 6.9): For any rate $R \in (0, 1)$ and any small constant $\tau > 0$ , there exists an explicit family of codes $C \subseteq \Sigma^N$ with constant alphabet size $|\Sigma| = O(1)$ that are:
- List-decodable (and list-recoverable) up to radius $\rho = 1 - R - \tau$ .
- Decodable deterministically in time $N^{1+\tau}$ and space $N^\tau$ .
- Capable of outputting a constant-sized list of codewords.
Deterministic Local Codes (DLLRCs): The authors formalize the notion of DLLRCs, where a global pre-processing step generates a list of deterministic local algorithms. They demonstrate that DLLRCs behave well under standard coding theory transformations, including:
- Intersection (with DLCCs).
- Concatenation (to reduce alphabet size).
- AEL distance amplification.
- Tensoring.
High-Rate Base Constructions:
- Construction of a high-rate DALLRC using tensor codes and a specific base code derived from graph-based codes [ST25a].
- Construction of a high-rate DLCC using Lifted Reed-Solomon codes, adapted to ensure the rate is arbitrarily close to 1 (improving upon the rate $\ge 1/2$ guarantee in [CM25]).

Significance and Claims

The paper claims to resolve the open problem of constructing deterministic, time- and space-efficient list-decoding algorithms that achieve capacity.

Overcoming Randomization: The work challenges the "common wisdom" that local list-decoding must be randomized. By introducing the concept of deterministic local list-recovery with pre-processing, the authors show that locality and determinism can coexist if the pre-processing is allowed to be global but resource-efficient.
Bridging the Gap: Prior to this work, there was a dichotomy: algorithms were either capacity-achieving but required linear space or were randomized; or they were deterministic and low-space but achieved only low rates. This paper unifies these properties.
Utility of DLLRCs: The authors posit that the explicit definition and manipulation of DLLRCs as black-box objects (via intersection, concatenation, etc.) is a valuable contribution in itself, potentially useful for future applications in pseudorandomness and cryptography where deterministic, low-space primitives are desirable.

The paper does not claim to improve the asymptotic time complexity beyond $N^{1+\tau}$ (which is near-linear) or space beyond $N^\tau$ (sublinear), but rather establishes that these bounds are achievable simultaneously with capacity-achieving parameters in a deterministic setting.