AI & ML
A Universal Threshold Theory for Local Properties of Random Linear Codes
arXiv math.IT0 views
arXiv:2611.07661v1 Announce Type: new Abstract: 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 threshold. This is the dimension predicted by the best union bound over covers of $\mathcal P$: families of subspaces such that the span of every witness contains at least one member. This gives a general derandomization statement: Any decreasing local property satisfied by RLCs at a given rate holds at a similar rate for pseudorandom ensembles that fool the cover union bound. In addition to previously studied ensembles, these include codes whose parity-check matrix is sampled from a small-bias distribution. Because our threshold characterization applies to all local properties, this derandomization also reaches properties beyond the scope of earlier reductions, including maximum loads in linear hashing for arbitrary input sets, rank-metric list decoding, and list decoding from insertion-deletion errors and burst errors. Our theorem unifies and strengthens prior works on row-symmetric and coordinate-wise linear characterizations, which located the threshold to within $O(q^{2b}\log_q n)$ and $O(b^2+nb/\log_2 q)$ dimensions, respectively. We obtain $O(b)$ error for every $b$-local property, independently of alphabet size. Under suitable pseudorandomness bounds, the rate loss vanishes for every $b=o(n)$, compared to $b=O(\log n)$ for earlier frameworks.
Source:https://arxiv.org/abs/2611.07661PreviousCombinatorial limitations of list-decoding Reed-Solomon codesNextOver-the-Scene Computation: Illumination-Programmed Functional Sensing of Unresolvable Populations
Related posts
Metaの150億ドル調達が支える、Quest上の「臨床補完」VRアプリ開発のリアル — AmblyoPunchから見えるインフラの価値(lazy eye / 弱視 / 両眼視 / VR vision training)
0dev.to
Why "AI" ends up as the biggest category on a launch board
0dev.to
Phân tích tương quan Atletico Madrid - Barcelona: Khi hàng công bùng nổ chạm trán bức tường phòng ngự
0dev.to Data

Thống kê bóng đá Anh: Blackpool vượt ải nhọc nhằn, biến số khó lường tại Championship
0dev.to Data
Phân tích dữ liệu Espanyol 0-0 Deportivo La Coruna: Điểm tựa Leo Román và sự bế tắc của đội chủ nhà
0dev.to Data

Đánh Giá Dữ Liệu Fulham 1-1 Newcastle: Tối Ưu Hiệu Quả Từ Băng Ghế Dự Bị
0dev.to Data