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-\Theta(\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(\mathcal{O}(\varepsilon^{-3/2}\log^2(1/\varepsilon))$, computational complexity of encoding/decoding $n^{\mathcal{O}(\varepsilon^{-1}\log(1/\varepsilon))}$, storage complexity $\mathcal{O}(n^{\eta+1}\log n)$ for a code design parameter $\eta>1$ that trades off storage complexity with the probability of error. The error probability is $\mathcal{O}(n^{-\eta})$, and the (vanishing) feedback rate is $\mathcal{O}(1/ \log n)$.

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