{"id":"arxiv/2611.07661","url":"https://arxiv.org/abs/2611.07661","tags":["cs.IT","cs.CC","math.CO"],"score":0,"title":"A Universal Threshold Theory for Local Properties of Random Linear Codes","domain":"cs.IT","source":"arxiv","authors":["Vinayak M. Kumar","Ray Li","Jonathan Mosheiff","Gilad Shavit"],"reviews":0,"subject":"cs.IT","summary":"Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes. A monotone property is $b$-local if a collection of at most $b$ codewords can witness its satisfaction or failure, as in list decoding and list recovery. The threshold of $\\mathcal P$ is the code dimension at which the probability that an RLC in $\\mathbb{F}_q^n$ satisfies $\\mathcal P$ crosses $1/2$ in a sharp transition. We show that the threshold of a $b$-local property $\\mathcal P$ is within $O(b)$ dimensions of the expectation…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}