🔢 mathematics

Time- and Space-Efficient List Decoding up to Capacity

本文提出了一种列表可译码码的构造方法，该方法在保持常数输出列表大小和字母表大小的同时，实现了容量，且其确定性时间复杂度与空间复杂度分别为 $N^{1+\tau}$ 和 $N^{\tau}$ 。

原作者： Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters

发布于 2026-08-18

📖 1 分钟阅读🧠 深度阅读

原作者： Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在数字世界中，信息是脆弱的。当数据在网络中传输或存储在硬盘上时，它不断受到噪声、干扰和损坏的威胁。一个比特位的翻转就可能将清晰的图像变成静电噪声，或将一笔正确的银行转账变成损失的金额。为了应对这一问题，工程师们使用纠错码，这本质上是数学配方，在发送消息之前向其中添加额外的冗余信息。这种冗ر余信息就像是一个安全网，允许接收方即使在部分数据受损的情况下也能重建原始消息。几十年来，目标一直是让这些安全网尽可能高效：在能够修复尽可能多错误的同时，添加最少的额外数据。这种效率的理论极限被称为“容量”。达到容量意味着一种编码的表现已经达到了物理和数学所允许的最佳水平，即在给定量级的额外数据下，能够修正最大数量的错误。

然而，该领域还存在着第二个经常被忽视的挑战：运行解码过程所需的物理资源。虽然现代计算机速度极快，但它们也受限于同时能容纳多少内存。近年来发现的一些最强大的解码方法虽然速度极快，但需要海量的内存才能运行，这使得它们对于卫星、传感器或安全硬件等约束严苛的设备来说并不实用。此外，许多高效的方法依赖于随机性——使用抛硬币或随机种子来引导解码过程。虽然随机性在理论上行之有效，但在对可预测性和安全性要求极高的现实系统中，它却是一种隐患。确定性算法（即遵循严格、不变路径且不进行随机选择的算法）对于构建可靠、安全且可重现的系统更为理想。

一支研究团队现在弥合了这些相互竞争的需求之间的鸿隙。他们构建了一种新型纠错码家族，这种编码不仅达到了理论上的最大效率，而且其解码算法既是确定性的，又对内存极其节省。他们的工作证明，可以在不需要大量内存或依赖随机性的情况下，实现接近代码所能处理的错误上限。他们开发的算法运行时间几乎与数据规模呈线性关系，这意味着它可以高效扩展，但使用的内存仅为以往高性能方法所需内存的一小部分。这是一个显著的转变，因为它表明，高性能并不一定非要以牺牲内存或确定性为代价。

其核心成就源于对解码方式的一种巧妙重构。传统上，解码受损消息涉及同时观察整个消息以寻找原始信息。这种全局视角功能强大，但非常消耗内存。另一种“局部”解码则一次只观察消息的一个微小部分，虽然节省内存，但通常需要通过随机性才能正常工作。研究人员意识到，通过允许一个在实际解码开始前进行的微小且高效的预处理步骤，他们可以让这个局部过程变为确定性的。可以将这种预处理想象成一个一次性的设置过程，解码器在此过程中准备好地形图；一旦地图准备就绪，实际的解码旅程就可以以完全确定的方式逐步进行，且仅需极少的内存，而无需再次观察全局图景。

为了构建这个系统，研究人员使用了一种被称为张量码（tensor code）的结构，它可以被可视化为一个多维数据网格，其中每一行和每一列都必须遵循特定的规则。他们开发了一种在网格中导航的新方法。该算法并非试图一次性解码整个网格，而是将问题分解为更小、更易处理的部分。它使用一种技术来选择网格中的几个代表性列并对其进行解码，然后利用这些信息推断出其余部分。至关重要的是，他们设计了一种方法，可以在不将整个网格存储在内存中的情况下，验证这些推断的正确性。他们创建了一系列测试，充当质量控制检查，确保解码的部分能够正确拼接并与接收到的数据相匹配，同时仅占用极小的空间。

结果是一个既强大又实用的系统。他们构建的编码可以针对任何期望的数据传输速率实现达到理论极限（即容量）的错误纠正。其解码算法的运行时间几乎与消息长度成正比，足以应对实时应用。最重要的是，它使用的内存随消息规模增长得非常缓慢，这意味着它可以处理海量数据而不会耗尽空间。这与以往的方法形成了鲜明对比，因为以往的方法要么为了速度牺牲内存，要么依赖随机性，或者无法达到理论上的效率极限。通过将高率基码与一种新型确定性局部解码相结合，研究人员展示了可以在速度、内存和可靠性之间克服权衡难题。

这项工作还解决了计算机科学中的一个基本问题：高效计算究竟需要多少随机性？长期以来，人们一直认为某些类型的局部解码在本质上无法实现确定性。研究人员表明，这种观点是基于一种并未考虑到微小、高效预处理步骤的特定“局部性”定义。通过稍微放宽这一定义，他们释放了创建与随机算法同样强大的确定性算法的能力。这一洞察为密码学和安全通信等领域开启了大门，在这些领域中，确定性行为通常是严格的要求。这种能够以确定方式、使用极少资源且无需随机种子的解码数据能力，为构建稳健数字系统提供了新的基础。

这项发现的影响超出了仅仅修复损坏文件的范畴。用于构建这些编码的技术（例如他们结合不同类型编码的具体方式以及剔除错误可能性的方法）是可应用于编码理论中其他问题的通用工具。研究人员证明，他们的方法不仅适用于简单的纠错，还适用于一项更复杂的任务——列表恢复（list recovery），其目标是找到可能导致受损信号的所有原始消息。这种多功能性表明，他们揭示的底层原理是稳健且广泛适用的。

在更广泛的计算背景下，这项工作代表了迈向更高效、更可靠数字基础设施的一步。随着数据量的持续爆炸式增长，能够快速处理信息而不压榨内存的算法变得日益重要。能够在保持紧凑内存约束的同时实现最佳纠错能力，意味着未来的设备可以做得更小、更安全、功能更强。研究人员提供了一个构建此类系统的蓝图，证明了效率的理论极限不仅是数学上的抽象概念，也是计算机物理世界中可以实现的现实。他们在创造出一个达到容量的确定性、空间高效型解码器方面取得的成功，标志着在持续努力使数字通信更具韧性和效率的过程中，迈出了重要的里程碑。

以下是技术摘要的中文翻译：

技术摘要：达到容量极限的实时、低空间列表译码技术

问题陈述

本文致力于构建能够实现速率 ( $R$ ) 与列表译码半径 ( $\rho$ ) 之间最优权衡（即达到容量）的纠错码。具体而言，作者寻求能够实现直到半径 $\rho \approx 1 - R$ 的常数大小列表译码的码，同时满足两个严苛的效率约束：

时间效率： 译码算法必须在近线性时间内运行（对于任意微小的 $\tau > 0$ ，为 $N^{1+\tau}$ ）。
空间效率： 译码算法必须使用亚线性空间（ $N^\tau$ ）。

虽然先前的研究已经实现了具有近线性时间的容量级列表译码，但这些算法要么是随机化的，要么需要线性空间。相反，最近的确定性低空间算法（例如 Cook 和 Moshkovitz [CM26]）虽然实现了亚线性空间，但在速率上远未达到容量。核心挑战在于构建既能实现时间效率又能实现空间效率，同时又能接近容量的确定性算法。

方法论与技术路径

作者的方法核心在于构建确定性局部列表恢复码 (Deterministic Locally List-Recoverable Codes, DLLRCs)。他们观察到，纯粹的局部确定性列表译码是不可能的（因为对手可以破坏局部算法查询的少数坐标），但如果允许算法在开始局部查询之前进行少量的全局预处理（亚线性空间和近线性时间），那么“确定性局部”的概念就变得可行。

该构造过程分为三个主要阶段：

1. 通过张量码实现确定性近似局部列表恢复 (DALLRC)

其核心技术引擎是针对张量码（Tensor Codes）的确定性版本随机局部列表恢复算法，该算法最初由 Haeupler, Reich, 和 Wootters [HRW19] 开发。

张量码： 作者构造了代码 $C^{\otimes t}$ （基础码 $C$ 的张量积）。
去随机化： 他们通过遍历采样器（一种伪随机对象）的所有种子，对用于递归译码过程的列的选择进行去随机化。
剪枝伪候选集： 直接的去随机化会导致候选局部算法的数量呈指数级增长。为了保持常数大小的列表，作者引入了一套由三个低空间确定性测试器（ $Test_1, Test_2, Test_3$ $T es t_{1}, T es t_{2}, T es t_{3}$ ）组成的工具，在预处理期间对列表进行剪枝：
- $Test_1$ ：验证候选字符串是否接近代码 $C^{\otimes t}$ 。
- $Test_2$ ：验证候选字符串是否接近输入列表 $S$ 。
- $Test_3$ ：确保候选对象与之前接受的候选对象不同。
近似性： 最终得到的算法是一种近似 DALLRC，这意味着它在 $1-\epsilon$ 的坐标上正确恢复码字，而非 100%。

2. 从近似到精确：与 DLCC 的交集

为了消除近似误差 ( $\epsilon$ ) 并实现精确恢复，作者将高速率的 DALLRC 与确定性局部可纠错码 (Deterministic Locally Correctable Code, DLCC) 进行求交。

他们利用了一种基于提升 Reed-Solomon 码 (Lifted Reed-Solomon codes) 的高速率 DLCC 构造，并借鉴了 Cook 和 Moshkovitz [CM25] 的结果。
通过将处理大部分列表恢复任务的 DALLRC 与处理剩余 $\epsilon$ 部分错误的 DLCC 相结合，他们获得了一种高速率的精确 DLLRC。

3. 通过 AEL 距离放大实现容量

上述构建的高速率 DLLRC 的译码半径仍然小于容量极限。为了达到容量，作者应用了 Alon-Edmonds-Lubby (AEL) 距离放大变换。

该变换基于二部扩展图，可以将高速率码的译码半径提升至接近 $1-R$ 。
至关重要的是，作者证明了 AEL 变换保留了底层 DLLRC 的确定性、低空间和近线性时间的特性。

主要贡献与结果

本文提出了以下主要结果：

主定理 (Theorem 1.2 / Corollary 6.9)： 对于任何速率 $R \in (0, 1)$ 和任何微小常数 $\tau > 0$ ，存在一族显式的码 $C \subseteq \Sigma^N$ ，其字母表大小 $|\Sigma| = O(1)$ 为常数，且满足：
- 在半径 $\rho = 1 - R - \tau$ 下具有列表译码（及列表恢复）能力。
- 可以以 $N^{1+\tau}$ 的时间复杂度和 $N^\tau$ 的空间复杂度进行确定性译码。
- 能够输出常数大小的码字列表。
确定性局部码 (DLLRCs)： 作者形式化了 DLLRC 的概念，其中全局预处理步骤生成一个确定性局部算法列表。他们证明了 DLLRC 在标准的编码理论变换下表现良好，包括：
- 交集（与 DLCCs）。
- 连接（以降低字母表大小）。
- AEL 距离放大。
- 张量积。
高速率基础构造：
- 使用张量码和源自图码 [ST25a] 的特定基础码构造高速率 DALLRC。
- 使用提升 Reed-Solomon 码构造高速率 DLCC，通过调整确保速率可以任意接近 1（改进了 [CM25] 中速率 $\ge 1/2$ 的保证）。

意义与主张

本文声称解决了构建能够达到容量的确定性、时空高效的列表译码算法这一开放问题。

克服随机性： 这项工作挑战了“局部列表译码必须是随机化”的普遍共识。通过引入“带有预处理的确定性局部列表恢复”概念，作者表明，如果允许预处理是全局性的但资源消耗高效，那么局部性和确定性是可以共存的。
弥合差距： 在此工作之前，存在一种二分现象：算法要么是容量级的但需要线性空间或具有随机性；要么是确定性的且低空间的但只能实现低速率。本文统一了这些特性。
DLLRCs 的效用： 作者认为，将 DLLRC 作为黑盒对象进行显式定义和操作（通过交集、连接等）本身就是一个有价值的贡献，对于未来在需要确定性、低空间原语的伪随机性和密码学领域的应用可能具有重要意义。

本文并未声称在渐近时间复杂度上超越了 $N^{1+\tau}$ （即近线性）或在空间上超越了 $N^\tau$ （即亚线性），而是确立了在确定性设定下，这些界限可以与容量级参数同时实现。