論文の概要: Affine Combiners for Reed-Solomon Proximity Gaps
- arxiv url: http://arxiv.org/abs/2611.15128v1
- Date: Wed, 11 Nov 2026 07:13:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.071525
- Title: Affine Combiners for Reed-Solomon Proximity Gaps
- Title(参考訳): リード・ソロモン近接ガス用アフィンコンバイン
- Abstract要約: 我々は、ランダムな組み合わせによって受信した単語をテストするプロトコルの音質保証を証明した。
$mathbbF_q$上の$n$符号の場合、古典的なスカラーコンバインダーは、一意復号方式でエラー$O(n/q)$を達成する。
- 参考スコア(独自算出の注目度): 45.14802220726878
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reed-Solomon proximity gaps establish soundness guarantees for protocols that test received words through random combinations. For length-$n$ codes over $\mathbb{F}_q$, classical scalar combiners achieve error $O(n/q)$ in the unique-decoding regime, with larger known bounds near the Johnson radius. We prove smaller error bounds using affine combiners, which combine two received words $f,g$ as $f(x)+(α+βx)g(x)$, where $α,β$ are independent uniform elements of $\mathbb{F}_q$. For output degree bound $d=ρn$, fixed $ρ\in(0,1)$ and $0<η<1-\sqrtρ$, and sufficiently large block length $n$, we prove mutual correlated agreement (MCA) with one coordinate of agreement loss at threshold $A=\lceil(\sqrtρ+η)n\rceil$, with error $O_{ρ,η}\left(\frac{1}{q}+\frac{n^2}{q^2}\right)$. The result holds over arbitrary evaluation domains in every finite field, including prime and binary extension fields. The agreement threshold can approach the Johnson threshold, beyond unique decoding. For $q\ge n^2$, our error is $O_{ρ,η}(1/q)$, an asymptotic factor-$n$ separation from scalar combiners: we prove that their worst-case MCA error is $Ω_{ρ,η}(n/q)$ at the same agreement threshold and with the same one-coordinate loss. We also prove that affine combiners incur worst-case error $Ω_{ρ,η}(n/q)$ when no agreement loss is allowed. Thus one coordinate of agreement loss is necessary for our guarantee; this relaxation of standard MCA reduces the guaranteed common agreement fraction by at most $1/n$. We also extend the result to $k$-variate Reed-Muller codes on subfield grids, obtaining MCA error $O_{ρ,η,k}(q^{-k})$ for fixed $ρ,η,k$, sufficiently large $n$, and $q\ge n^{k+1}$, with agreement loss $n^{1-1/k}$.
- Abstract(参考訳): リード・ソロモン近接ギャップは、ランダムな組み合わせによって受信した単語をテストするプロトコルの音質保証を確立する。
長さ$$$$$$$$$$\mathbb{F}_q$ の場合、古典的なスカラーコンバインダーは、ジョンソン半径に近いより大きな境界を持つ一意復号法で誤り$O(n/q)$を得る。
より小さな誤差境界は、f,g$ を $f(x)+(α+βx)g(x)$ とし、$α,β$ を $\mathbb{F}_q$ の独立一様元とする。
d=ρn$, fixed $ρ\in(0,1)$, $0<η<1-\sqrtρ$, and enough large block length $n$, we prove mutual correlation agreement (MCA) with one coordinate of agreement loss at threshold $A=\lceil(\sqrtρ+η)n\rceil$, with error $O_{ρ,η}\left(\frac{1}{q}+\frac{n^2}{q^2}\right)$。
結果は素拡大体や二項拡大体を含むすべての有限体における任意の評価領域を保持する。
合意しきい値は、ユニークな復号化を超えてジョンソンしきい値に近づくことができる。
例えば、$q\ge n^2$の場合、我々の誤差は$O_{ρ,η}(1/q)$, asymsymotic factor-$n$ from scalar Combinrs: we prove that the worst-case MCA error is $Ω_{ρ,η}(n/q)$ at the same agreement threshold and with the same one-coordinate loss。
また、アフィン結合器が最悪の場合のエラーを$Ω_{ρ,η}(n/q)$で発生させることも証明する。
したがって、我々の保証には合意損失の1つの座標が必要であり、標準MCAの緩和は保証された共通合意率を少なくとも1/n$に下げる。
さらに、サブフィールドグリッド上のReed-Muller符号を$k$-variateに拡張し、固定された$ρ,η,k$,十分に大きな$n$,$q\ge n^{k+1}$に対してMCAエラー$O_{ρ,η,k}(q^{-k})$を得る。
関連論文リスト
- Multivalued Consensus: General Adversaries Require More Communication [34.662213518530315]
我々は,一般敵(非攻撃者)に対する$n$のフォールトトレラントコンセンサスについて検討する。
無限族 $Z_mathsfprojn,d$ of $Qd$-satisfying $n$-party 逆構造を記述する。
論文 参考訳(メタデータ) (2026-08-18T16:46:15Z) - Optimal Temporal Hiding in Correlated Quantum Reference-Frame Processes [0.0]
$[n,k]_q$コードの一様コセット法則は、$d(Cperp)$スロット以下のすべての集合で同一である。
ネストされたコードに対して$Csubset D$、ペイロード$R=dim D-dim C$、見えない深さ$t=d_mathrmrel(Cperp,Dperp)-1$、セクター距離$d_mathrmrel(D,C)-1leq n$。
論文 参考訳(メタデータ) (2026-08-06T06:27:12Z) - PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。
我々はアルゴリズムをほぼ一致する下界で補完する。
論文 参考訳(メタデータ) (2025-02-20T18:32:02Z) - Asynchronous Approximate Agreement with Quadratic Communication [35.73648103944158]
非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。
Abraham, Amit and Dolev [OPODIS '04] はこの問題を最適なレジリエンス $t fracn3$ で $mathbbR$ で解く。
これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
論文 参考訳(メタデータ) (2024-08-10T09:03:06Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳(メタデータ) (2020-09-21T04:13:34Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳(メタデータ) (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。