← 研踪 PaperTrailarXiv: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
摘要
Given a channel with length- inputs and outputs over the alphabet , and of which a fraction 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 , we provide the first schemes that attain this performance for any , 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 and our minimal feedback scheme has the following parameters: Rate (i.e., -close to information-theoretically optimal -- here is the -ary entropy function), list-size , computational complexity of encoding/decoding , storage complexity for a code design parameter that trades off storage complexity with the probability of error. The error probability is , and the (vanishing) feedback rate is . 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v4 · 2026-11-17 20:01 · 最新观测版本
Efficient and rate-optimal list-decoding in the presence of minimal feedback
Given a channel with length- inputs and outputs over the alphabet , and of which a fraction 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 , we provide the first schemes that attain this performance for any , 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 and our minimal feedback scheme has the following parameters: Rate (i.e., -close to information-theoretically optimal -- here is the -ary entropy function), list-size , computational complexity of encoding/decoding , storage complexity for a code design parameter that trades off storage complexity with the probability of error. The error probability is , and the (vanishing) feedback rate is . 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.
查看此版本解读 →查看此版本原文 ↗