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
Show HN: Sidekick AI – A local-first VS Code extension with hybrid vector search
0Hacker News Show
Show HN: BoxRouter – OpenRouter for Sandboxes
0Hacker News Show
Show HN: Hosting Market Insights – 97.3% of domains mapped to 8,300 providers
0Hacker News Show
Show HN: Werkbank – 40 tool-using tasks to evaluate self-hosted LLMs
0Hacker News Show
Show HN: MailScope – Catch and lint your app's dev emails locally on a Mac
0Hacker News Show
Microsoft’s new Licensed Weights lets businesses customize AI models with their own data
0ZDNet