{"id":"arxiv/2607.19576","url":"https://arxiv.org/abs/2607.19576","tags":["cs.IT","math.CO"],"score":0,"title":"Bounds and Limitations on Codes Achieving List Recovery Capacity","domain":"cs.IT","source":"arxiv","authors":["Joshua Brakensiek","Yeyuan Chen","Aaron Putterman","Zihan Zhang"],"reviews":0,"subject":"cs.IT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}