Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep's clothing

Abstract

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

Abstract shortened to meet the arXiv requirement