跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2511.04088 · v4

Efficient and rate-optimal list-decoding in the presence of minimal feedback

首次提交 2025-11-06 13:58
版本更新 2026-11-17 20:01
雷达观测 2026-11-18 11:33
arXiv ↗PDF ↗

摘要

Given a channel with length-nn inputs and outputs over the alphabet {0,1,…,q−1}\{0,1,\ldots,q-1\}, and of which a fraction ϱ∈(0,1−1/q)\varrho \in (0,1-1/q) of symbols can be arbitrarily corrupted by an adversary, a fundamental problem is that of communicating at rates close to the information-theoretically optimal values, while ensuring the receiver can infer that the transmitter's message is from a ``small" set. While the existence of such codes is known, and constructions with computationally tractable encoding/decoding procedures are known for large qq, we provide the first schemes that attain this performance for any q≥2q \geq 2, as long as low-rate feedback (asymptotically negligible relative to the number of transmissions) from the receiver to the transmitter is available. For any sufficiently small ε>0\varepsilon > 0 and ϱ∈(1−1/q−Θ(ε))\varrho \in (1-{1}/{q}-Θ(\sqrt{\varepsilon})) our minimal feedback scheme has the following parameters: Rate 1−Hq(ϱ)−ε1-H_q(\varrho) - \varepsilon (i.e., ε\varepsilon-close to information-theoretically optimal -- here Hq(ϱ)H_q(\varrho) is the qq-ary entropy function), list-size exp⁡(O(ε−3/2log⁡2(1/ε)))\exp\left(\mathcal{O}\left(\varepsilon^{-3/2}\log^2(1/\varepsilon)\right)\right), computational complexity of encoding/decoding nO(ε−1log⁡(1/ε))n^{\mathcal{O}(\varepsilon^{-1}\log(1/\varepsilon))}, storage complexity O(nη+1log⁡n)\mathcal{O}(n^{η+1}\log n) for a code design parameter η>1η>1 that trades off storage complexity with the probability of error. The error probability is O(n−η)\mathcal{O}(n^{-η}), and the (vanishing) feedback rate is O(1/log⁡(n))\mathcal{O}({1}/{\sqrt{\log(n)}}). Our full-feedback scheme has zero probability of error and minimal storage complexity, while the other parameters are the same as the vanishing rate feedback scheme.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v4,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v4 · 2026-11-17 20:01 · 最新观测版本

Efficient and rate-optimal list-decoding in the presence of minimal feedback

Given a channel with length-nn inputs and outputs over the alphabet {0,1,…,q−1}\{0,1,\ldots,q-1\}, and of which a fraction ϱ∈(0,1−1/q)\varrho \in (0,1-1/q) of symbols can be arbitrarily corrupted by an adversary, a fundamental problem is that of communicating at rates close to the information-theoretically optimal values, while ensuring the receiver can infer that the transmitter's message is from a ``small" set. While the existence of such codes is known, and constructions with computationally tractable encoding/decoding procedures are known for large qq, we provide the first schemes that attain this performance for any q≥2q \geq 2, as long as low-rate feedback (asymptotically negligible relative to the number of transmissions) from the receiver to the transmitter is available. For any sufficiently small ε>0\varepsilon > 0 and ϱ∈(1−1/q−Θ(ε))\varrho \in (1-{1}/{q}-Θ(\sqrt{\varepsilon})) our minimal feedback scheme has the following parameters: Rate 1−Hq(ϱ)−ε1-H_q(\varrho) - \varepsilon (i.e., ε\varepsilon-close to information-theoretically optimal -- here Hq(ϱ)H_q(\varrho) is the qq-ary entropy function), list-size exp⁡(O(ε−3/2log⁡2(1/ε)))\exp\left(\mathcal{O}\left(\varepsilon^{-3/2}\log^2(1/\varepsilon)\right)\right), computational complexity of encoding/decoding nO(ε−1log⁡(1/ε))n^{\mathcal{O}(\varepsilon^{-1}\log(1/\varepsilon))}, storage complexity O(nη+1log⁡n)\mathcal{O}(n^{η+1}\log n) for a code design parameter η>1η>1 that trades off storage complexity with the probability of error. The error probability is O(n−η)\mathcal{O}(n^{-η}), and the (vanishing) feedback rate is O(1/log⁡(n))\mathcal{O}({1}/{\sqrt{\log(n)}}). Our full-feedback scheme has zero probability of error and minimal storage complexity, while the other parameters are the same as the vanishing rate feedback scheme.

查看此版本解读 →查看此版本原文 ↗