Bounds and Limitations on Codes Achieving List Recovery Capacity
In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code. More formally, given a code $C \subseteq Σ^n$ and input lists $S_1, \dots, S_n \subseteq Σ$ of size at most $\ell$, list recoverability requires that there are at most $L$ codewords $c \in C$ such that $c_i \in S_i$ for at least $(1-ρ)n$ choices of $i \in [n]$. List recovery is an important question which has found applications in many areas, including complexity theory, property testing, compressed sensing, streaming algorithms, and cryptography. As our first…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.19576
curl -X POST /api/v1/records/arxiv/2607.19576/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.19576/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'