Fugu-MT 論文翻訳(概要): Discrepancy for Random Linear Codes

論文の概要: Discrepancy for Random Linear Codes

arxiv url: http://arxiv.org/abs/2606.24471v1
Date: Tue, 23 Jun 2026 12:01:54 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-24 22:16:48.936727
Title: Discrepancy for Random Linear Codes
Title（参考訳）: ランダム線形符号の離散性
Authors: Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro,
Abstract要約: ランダムな線形符号は、幅広い状況下でほぼ最適な相違性を持つことを示す。まず、ランダムな線形符号は、容量以上のエラーからリスト復号する非構造化のランダム符号と一致する。第二に、素体上のランダム線形符号はゼロエラーリストのキャパシティ上の非構造化ランダム符号と一致する。
参考スコア（独自算出の注目度）: 10.105438043325357
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates of a fixed test, and another controlling large families of Fourier-pseudorandom tests. Two motivating applications follow. First, random linear codes match unstructured random codes for list-decoding from errors above capacity. If $C\subseteq\mathbb F_q^n$ is a random linear code of rate $1-\frac1n\log_q |B_ρ|+ε$, where $B_ρ$ is a radius-$ρ$ Hamming ball, then with high probability $$ |C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n} $$ simultaneously for all radius-$ρ$ Hamming balls $B\subseteq\mathbb F_q^n$. This extends the classical result that such codes have covering radius at most $ρn$ whp (Blinovsky, 1987). Second, over prime fields, random linear codes match unstructured random codes for zero-error list-recovery above capacity. For prime $q>2$ and $2\le \ell\le q-1$, a random linear code of rate $1-\log_q\ell+ε$ satisfies, with high probability, $$ |C\cap S|=(1\pm o(1))\frac{|C|\ell^n}{q^n} $$ simultaneously for all rectangles $S=S_1\times\cdots\times S_n$ with $|S_i|=\ell$. As a consequence, there are abundant $n$-party linear ramp secret sharing schemes over $\mathbb F_q$ with privacy threshold about $n/(2\log q)$ and reconstruction threshold about $5n/(2\log q)$, resilient to balanced local leakage; prior existence results required thresholds above $n/2$ even in this case. The translate result, hence the list-decoding application, holds over arbitrary finite fields, even growing with $n$. The list-recovery and leakage applications hold over prime fields under moderate growth, e.g. $q\le n^{1/5-o(1)}$. The proofs use a refined second-moment analysis tracking intersection sizes as random generators are added to $C$.
Abstract（参考訳）: ランダムな線形符号は、幅広い状況下でほぼ最適な相違性を持つことを示す。我々の主な結果は2つの一般的な定理である: 1つは固定テストのすべての変換を制御し、もう1つはフーリエ・プシュードロームテストの大きなファミリーを制御している。 2つのモチベーションがある。まず、ランダムな線形符号は、容量以上のエラーからリスト復号する非構造化のランダム符号と一致する。もし$C\subseteq\mathbb F_q^n$ が1-\frac1n\log_q |B_ρ|+ε$ のランダム線型符号であれば、$B_ρ$ は半径-$ρ$ Hamming ball であり、高い確率で $$ |C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n} $$ はすべての半径-$ρ$ Hamming balls $B\subseteq\mathbb F_q^n$ に対して同時に得られる。これは、これらの符号が半径を少なくとも$ρn$wp (Blinovsky, 1987) でカバーする古典的な結果を拡張する。第二に、素体上のランダム線形符号はゼロエラーリストのキャパシティ上の非構造化ランダム符号と一致する。 a random linear code of rate $1-\log_q\ell+ε$ with high probability, $$ |C\cap S|=(1\pm o(1))\frac{|C|\ell^n}{q^n} $$ for all rectangles $S=S_1\times\cdotsS_n$ with $|S_i|=\ell$。その結果、プライバシしきい値が約$n/(2\log q)$と復元しきい値が約$5n/(2\log q)$、バランスの取れたローカルリークに対して回復力を持つ、$n$のパーティーリニアランプシークレット共有スキームが、$\mathbb F_q$よりも多く存在する。その結果、リスト復号化アプリケーション(英語版)は任意の有限体を持ち、$n$で成長する。リストの回復とリークのアプリケーションは、中等成長の下で素体(例えば $q\le n^{1/5-o(1)}$)の上に保持する。それらの証明では、ランダムジェネレータが$C$に加算されるときに、交叉サイズを追跡する洗練された第2モーメント解析を使用する。

論文の概要: Discrepancy for Random Linear Codes

関連論文リスト