A Universal Threshold Theory for Local Properties of Random Linear Codes
Source: arxiv.org/abs/2611.07661
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.07661
curl -X POST /api/v1/records/arxiv/2611.07661/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.07661/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'