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 board faction angling for Jensen Huang return as CEO, report claims
0Tom's Hardware
New discovery reveals what may be holding back room-temperature superconductors
0Science Daily Tech
NASA pushes Mars helicopter blades beyond the speed of sound
0Science Daily Tech
How to make AI data centres more sustainable
0Nature News

The UK and some other countries don’t get more Siri AI usage with iCloud+
09to5Mac

MacPaw’s Moonlock comes to iPhone, helping users detect potential scams
09to5Mac