論文の概要: Improved LCL Equivalences and Curve Decoding Alphabet Sizes

• arxiv url: http://arxiv.org/abs/2610.38862v1
• Date: Wed, 28 Oct 2026 20:36:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-03 08:28:10.787843
• Title: Improved LCL Equivalences and Curve Decoding Alphabet Sizes
• Title（参考訳）: 改良されたLCL等価性とAlphabetサイズ曲線の復号化
• Abstract要約: LCL(Local Coordinate-wise Linear)プロパティは、リストのデコードやリストのリカバリといったコーディング理論の特性をキャプチャする。 各LCL特性がランダム線形符号(RLC)とランダムリード-ソロモン符号(RRS)に対して同じレート閾値を持つことを示す。 これらの結果を、曲線復号化のためのアルファベットサイズ境界に適用する。
• 参考スコア（独自算出の注目度）: 22.751490804310205
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local Coordinate-wise Linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025), capture coding-theoretic properties such as list decoding and list recovery. They showed that every LCL property has the same rate threshold for random linear codes (RLC) and random Reed--Solomon codes (RRS). Brakensiek, Chen, Dhar, and Zhang (2025) extended this to random additive codes. Thus any property of all subspace design codes holds for RLCs and RRS at the same rate. In this work, we improve the probabilistic guarantees in the RRS local equivalence theorem and extend the equivalence to all known subspace design constructions individually. Each such construction, including folded Reed--Solomon codes, has the same LCL threshold as RLC and RRS codes. We apply these results to alphabet-size bounds for curve decoding. Curve decoding, introduced by Goyal and Guruswami (2025) and Carmon et al. (2026), is a row-span-constrained LCL property implying proximity gaps (PG), correlated agreement (CA), and mutual correlated agreement (MCA), relevant to IOPs and SNARKs. Informally, a rate-$R$ code $C \subset \mathbb{F}^n$ is $(\ell,δ,a,b)$-curve decodable if any degree-$\ell$ curve $u:\mathbb{F}\to\mathbb{F}^n$ that is $δ$-close to $C$ on at least $a$ points has at least $b\leq a$ nearby codewords lying on a degree-$\ell$ curve in $C$. Goyal and Guruswami (2025) and Goyal, Guruswami, Sun, and Wootters (2026) established curve decodability for RLC and RRS codes at radius $δ$ approaching $1-R$, but with large alphabets in $\ell$ and $η:=1-R-δ$. Using our improved LCL equivalence and rank-sensitive counting inspired by Goyal and Guruswami (2026), we exponentially improve alphabet requirements while matching the best known values of $(a,b)$. For $\ell=O(1)$, our alphabet-size bounds match the best known for list decoding, and improves results for PG, CA, and MCA.
• Abstract（参考訳）: Levi, Mosheiff, Shagrithaya (2025) によって導入された局所コーディネート・ワイド・リニア(LCL)特性は、リストデコーディングやリストリカバリのような符号化理論の特性を捉えている。 彼らは、全てのLCL特性がランダム線形符号 (RLC) とランダムリードソロモン符号 (RRS) に対して同じレート閾値を持つことを示した。Brakensiek, Chen, Dhar, Zhang (2025) は、これをランダム加法符号に拡張した。したがって、すべての部分空間設計符号が同じレートで保持するすべての部分空間設計符号のプロパティは、RSR局所同値定理の確率的保証を改善し、各部分空間設計構造を個別に拡張する。Reed-Solomon符号を含む、それぞれの構成は、RCCとRS符号と同じLCL閾値を持つ。 これらの結果を、曲線復号化のためのアルファベットサイズ境界に適用する。 Goyal and Guruswami(2025年)とCarmon et al(2026年)によって導入された曲線復号法は、近接ギャップ(PG)、相関合意(CA)、相互相関合意(MCA)を暗示する行スパン制約のLCL特性である。 形式的には、$R$コード $C \subset \mathbb{F}^n$ is $(\ell,δ,a,b)$-curve deodable if any degree-$\ell$ curve $u:\mathbb{F}\to\mathbb{F}^n$ that is $δ$-close to $C$ on least $a$ points has least $b\leq a$ nearby codewords lying on a degree-$\ell$ curve in $C$。 Goyal and Guruswami (2025) と Goyal, Guruswami, Sun, and Wootters (2026) は、半径$δ$ で RLC と RRS の符号の曲線デオーダビリティを確立した。 2026年にGoyalとGuruswamiにインスパイアされた改良されたLCL同値とランクセンシティブカウントを用いて、最もよく知られた$(a,b)$とマッチングしながら、アルファベット要求を指数関数的に改善する。 $\ell=O(1)$の場合、我々のアルファベットサイズ境界はリスト復号法で最もよく知られたものと一致し、PG、CA、MCAの結果を改善する。

関連論文リスト

• Constant Rate Codes with Fully Addressable Transversal T: Good Codes, Sparse Checks [53.71337604556311]
  textbffully addressable $T$で優れたCSSコードを構築します。 また、Pauli-LDPCコードに$T$を与え、消滅率で距離を拡大します。 残る課題は、完全対応可能な非クリフォード1ビットゲートを持つ優れたPauli-LDPCコードを構築することである。
  論文  参考訳（メタデータ） (2026-09-30T05:11:17Z)
• Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs [3.027387890328427]
  正の定速度, 線形距離, 定音性を有する$r$次元立方体層を合成する。 r=4$と$k=2$を取ると、有界に良い二進数 qLTC の族が得られる。
  論文  参考訳（メタデータ） (2026-09-23T12:53:31Z)
• Proximity Gaps for Gabidulin Codes and Applications [25.766490264515806]
  すべての$[n,k,d]$リニアランクメトリックコード$C$ over $mathbb F_qm$は、エラー$$との近接ギャップを許容することを示している。 ガビデュリン符号の場合、誤差10qn-1/qmで$(d-1)/(2n)$にギャップを拡大する。 これら2つの近接ギャップは、一般的な線形ハミング計量符号とリードリーブド符号と一致する。 次に、LigeroベースのPCSを一般の人に適応させ、$q$を得る。
  論文  参考訳（メタデータ） (2026-09-09T07:45:54Z)
• CSS Quantum LRCs with Intersecting Recovery Sets: Constructions and Bounds [41.37063463693348]
  まず、基礎となる古典的符号が少なくとも2つの双対最小距離を持つと仮定すると、CSSコードは$(r,t,x)$-qLRCであることと、基礎となる古典的符号が共通のリカバリセットを持つ古典的LRC(cLRC)であることを示す。 次に、サブセット・インクルージョン・マトリックスを使用してバイナリ・デュアルを含む$(r,t,x)$-cLRCsのファミリを構築し、CSS構造を介して$(r,t,x)$-qLRCsを生成します。
  論文  参考訳（メタデータ） (2026-08-11T13:34:02Z)
• Locality of Curve-Decoding and Improved Proximity Gaps [22.751490804310205]
  確率ギャップ(英: Proximity gaps)は、対話型Oracle Proofs (IOPs) と Succinct Non-interactive Arguments of Zero Knowledge (SNARKs) の研究で生じる誤り訂正符号の特性である。 GoyalとGuruswamiの最近の研究は、多くの符号の族に対して、ほぼ最適な近接ギャップを確立している。
  論文  参考訳（メタデータ） (2026-07-09T14:10:58Z)
• Discrepancy for Random Linear Codes [10.105438043325357]
  ランダムな線形符号は、幅広い状況下でほぼ最適な相違性を持つことを示す。 まず、ランダムな線形符号は、容量以上のエラーからリスト復号する非構造化のランダム符号と一致する。 第二に、素体上のランダム線形符号はゼロエラーリストのキャパシティ上の非構造化ランダム符号と一致する。
  論文  参考訳（メタデータ） (2026-06-23T12:01:54Z)
• On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization [54.77408659142336]
  Kullback-Leibler (KL) の正規化は、オフラインの意思決定で広く使われている。 大規模な正規化の下では$tildeO(SAC*/)$のサンプル複雑性を実現する。 また、よりシャープなサンプル複雑性の下界も提供し、これは正規化強度の全範囲にわたる上界と一致する。
  論文  参考訳（メタデータ） (2026-05-04T01:46:35Z)
• Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
  本稿では,FSCLB(Federated Sketch Contextual Linear Bandits)を提案する。 合成と実世界の両方のデータセットの実験では、FSCLBは計算と通信のコストを90%以上削減している。
  論文  参考訳（メタデータ） (2026-05-01T08:22:06Z)
• Coxeter codes: Extending the Reed-Muller family [59.90381090395222]
  我々は、領域 $mathbbZm$ を任意の有限コクセター群に置き換えることで、RM族を一般化するバイナリ線形符号のクラスを導入する。 コクセター符号はまた、閉じた対角線Z$回転が非自明な論理を実行することができる量子符号の族を生じる。
  論文  参考訳（メタデータ） (2025-02-20T17:16:28Z)
• Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback [57.6775169085215]
  リスクに敏感な強化学習は、期待される報酬とリスクのバランスをとるポリシーを最適化することを目的としている。 本稿では,線形および一般関数近似の下で,CVaR(Iterated Conditional Value-at-Risk)を目標とする新しいフレームワークを提案する。 本稿では,この反復CVaR RLに対するサンプル効率の高いアルゴリズムを提案し,厳密な理論的解析を行う。
  論文  参考訳（メタデータ） (2023-07-06T08:14:54Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。