← 研踪 PaperTrailarXiv:2606.24471 · v3
Discrepancy for Random Linear Codes
首次提交 2026-06-23 20:01
版本更新 2026-11-02 21:40
雷达观测 2026-11-04 23:41
摘要
We show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one controls all translates of a fixed test, and the other controls large families of Fourier-pseudorandom tests. Two motivating examples follow: First, RLCs behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, an RLC $C\subseteq \mathbb{F}_q^n$ of rate $1 - \frac{1}{n}\log_q|B_ρ| + \varepsilon$, where $|B_ρ|$ is the volume of a radius-$ρ$ Hamming ball in $\mathbb{F}_q^n$, satisfies $|C \cap B| = (1\pm o(1)) \frac{|C|\cdot |B|}{q^n}$ simultaneously for all radius-$ρ$ Hamming balls $B$ with high probability. This significantly strengthens the best prior results, which follow from work by Blinovsky (1987, 1990) and Levitin (1988) on the covering properties of RLCs. Second, over prime fields, RLCs behave essentially like unstructured random codes for zero-error list-recovery, and list-recovery from erasures, above capacity. More precisely, for a prime $q>2$ and input list size $2\leq \ell\leq q-1$, an RLC $C\subseteq \mathbb{F}_q^n$ of rate $1-\log_q \ell+\varepsilon$ will satisfy $|C \cap S| = (1\pm o(1)) \frac{|C|\cdot \ell^n}{q^n}$ simultaneously for all combinatorial rectangles $S=S_1\times S_2\times\cdots\times S_n$, where $|S_i|=\ell$ for all $i$, with high probability. An analogous result also holds when we can bound $|S_i|$ only for some of the $i$'s. We use this to show the abundance of locally leakage-resilient $n$-party linear ramp secret sharing schemes with any linear reconstruction threshold and sublinear threshold gap $O(n/\log n)$ over fields of polynomial size $q=Θ(n^γ)$ for a constant $γ\in(0,1/5)$. Prior work was stuck at reconstruction thresholds above $n/2$ for both threshold and ramp schemes.
作者备注：66 pages. Updated discussion of related work
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-02 21:40 · 最新观测版本
Discrepancy for Random Linear Codes
We show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one controls all translates of a fixed test, and the other controls large families of Fourier-pseudorandom tests. Two motivating examples follow: First, RLCs behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, an RLC $C\subseteq \mathbb{F}_q^n$ of rate $1 - \frac{1}{n}\log_q|B_ρ| + \varepsilon$, where $|B_ρ|$ is the volume of a radius-$ρ$ Hamming ball in $\mathbb{F}_q^n$, satisfies $|C \cap B| = (1\pm o(1)) \frac{|C|\cdot |B|}{q^n}$ simultaneously for all radius-$ρ$ Hamming balls $B$ with high probability. This significantly strengthens the best prior results, which follow from work by Blinovsky (1987, 1990) and Levitin (1988) on the covering properties of RLCs. Second, over prime fields, RLCs behave essentially like unstructured random codes for zero-error list-recovery, and list-recovery from erasures, above capacity. More precisely, for a prime $q>2$ and input list size $2\leq \ell\leq q-1$, an RLC $C\subseteq \mathbb{F}_q^n$ of rate $1-\log_q \ell+\varepsilon$ will satisfy $|C \cap S| = (1\pm o(1)) \frac{|C|\cdot \ell^n}{q^n}$ simultaneously for all combinatorial rectangles $S=S_1\times S_2\times\cdots\times S_n$, where $|S_i|=\ell$ for all $i$, with high probability. An analogous result also holds when we can bound $|S_i|$ only for some of the $i$'s. We use this to show the abundance of locally leakage-resilient $n$-party linear ramp secret sharing schemes with any linear reconstruction threshold and sublinear threshold gap $O(n/\log n)$ over fields of polynomial size $q=Θ(n^γ)$ for a constant $γ\in(0,1/5)$. Prior work was stuck at reconstruction thresholds above $n/2$ for both threshold and ramp schemes.
查看此版本解读 →查看此版本原文 ↗