AI & ML
Efficient and rate-optimal list-decoding in the presence of minimal feedback
arXiv math.IT0 views
arXiv:2511.04088v4 Announce Type: replace Abstract: 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\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^{\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}/{\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.
Source:https://arxiv.org/abs/2511.04088PreviousFrames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codesNextOn concatenation of matrices for reversible linear codes over a finite commutative ring and applications to DNA codes
Related posts

Parallels Desktop review
0TechRadar
How Far Behind Are Open Weights, Measured
0dev.to
Claude was trained on protein sequences at scale
0Hacker News
Pretraining vs post-training: one apple problem, four learning signals
0dev.to Beginners
Bitcoin Recovery Expert USA: Professional Crypto Asset Recovery with META TECH RETRIEVE PRO
0dev.to Beginners
Hugging Face Switches Its Inference Providers to OpenRouter Routing
0dev.to OpenSource