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

NVIDIA RTX Spark Compact Desktops Out Now
0NVIDIA Blog

MacPaw's Moonlock Cybersecurity App Launches for iPhone
0MacRumors
Grand theft auto VI is an astonishing by American epic
0Hacker News New
Show HN: Globebug – A calm, conflict-safe travel OS for multi-city itineraries
0Hacker News New
Ask HN: Are you sick of buying domains
0Hacker News New
One missing, 11 injured after ADNOC vessel attacked in Strait of Hormuz
0Hacker News New