Given a channel with length-$n$ inputs and outputs over the alphabet $\{0,1,\ldots,q-1\}$, and of which a fraction $\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 $q$, we provide the first schemes that attain this performance for any $q \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 $\varepsilon > 0$ and $\varrho \in (1-{1}/{q}-Θ(\sqrt{\varepsilon}))$ our minimal feedback scheme has the following parameters: Rate $1-H_q(\varrho) - \varepsilon$ (i.e., $\varepsilon$-close to information-theoretically optimal -- here $H_q(\varrho)$ is the $q$-ary entropy function), list-size $\exp\left(\mathcal{O}\left(\varepsilon^{-3/2}\log^2(1/\varepsilon)\right)\right)$, computational complexity of encoding/decoding $n^{\mathcal{O}(\varepsilon^{-1}\log(1/\varepsilon))}$, storage complexity $\mathcal{O}(n^{η+1}\log n)$ for a code design parameter $η>1$ that trades off storage complexity with the probability of error. The error probability is $\mathcal{O}(n^{-η})$, and the (vanishing) feedback rate is $\mathcal{O}({1}/{\sqrt{\log(n)}})$.

翻译：给定一个输入输出字母表为$\{0,1,\ldots,q-1\}$、长度为$n$的信道，其中比例为$\varrho \in (0,1-1/q)$的符号可能被敌手任意篡改，一个核心问题是在保证接收方能推断出发送方消息来自一个“小”集合的前提下，实现接近信息论最优值的通信速率。虽然此类码的存在性已知，且针对大$q$值已存在具有计算可行编码/解码过程的构造，我们首次提出了适用于任意$q \geq 2$的方案，只要接收方向发送方提供低速率反馈（相对于传输次数渐近可忽略）。对于任意充分小的$\varepsilon > 0$和$\varrho \in (1-{1}/{q}-Θ(\sqrt{\varepsilon}))$，我们的最小反馈方案具有以下参数：速率$1-H_q(\varrho) - \varepsilon$（即$\varepsilon$接近信息论最优——此处$H_q(\varrho)$为$q$元熵函数），列表大小$\exp\left(\mathcal{O}\left(\varepsilon^{-3/2}\log^2(1/\varepsilon)\right)\right)$，编码/解码计算复杂度$n^{\mathcal{O}(\varepsilon^{-1}\log(1/\varepsilon))}$，存储复杂度$\mathcal{O}(n^{η+1}\log n)$（其中码设计参数$η>1$用于权衡存储复杂度与错误概率）。错误概率为$\mathcal{O}(n^{-η})$，反馈速率（趋近于零）为$\mathcal{O}({1}/{\sqrt{\log(n)}})$。