論文の概要: Improved Round-by-round Soundness IOPs via Reed-Muller Codes

• arxiv url: http://arxiv.org/abs/2504.00346v1
• Date: Tue, 01 Apr 2025 01:56:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-03 13:17:35.171837
• Title: Improved Round-by-round Soundness IOPs via Reed-Muller Codes
• Title（参考訳）: リード・ミューラー符号によるラウンド・バイ・ラウンド音質IOPの改良
• Authors: Dor Minzer, Kai Zhe Zheng,
• Abstract要約: IOPP (interactive Oracle proof of Near of Trivariate Reed-Muller codes) を提案する。 私たちのIOPPには、ラウンドバイラウンドのサウンドネス、$O(lambda)$クエリ、$O(loglog d)$ラウンド、$O(d)$長さがあります。 具体的には、Reed-Muller符号に近接生成器を与え、IOP構成におけるより体系的な「側条件処理方法」を示し、[Arnon, Chiesa, Fenzi, Yogev]のコンパイル手順を一般化する。
• 参考スコア（独自算出の注目度）: 0.3529736140137004
• License:
• Abstract: We give an IOPP (interactive oracle proof of proximity) for trivariate Reed-Muller codes that achieves the best known query complexity in some range of security parameters. Specifically, for degree $d$ and security parameter $\lambda\leq \frac{\log^2 d}{\log\log d}$ , our IOPP has $2^{-\lambda}$ round-by-round soundness, $O(\lambda)$ queries, $O(\log\log d)$ rounds and $O(d)$ length. This improves upon the FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] and the STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes, that have larger query and round complexity standing at $O(\lambda \log d)$ and $O(\log d+\lambda\log\log d)$ respectively. We use our IOPP to give an IOP for the NP-complete language Rank-1-Constraint-Satisfaction with the same parameters. Our construction is based on the line versus point test in the low-soundness regime. Compared to the axis parallel test (which is used in all prior works), the general affine lines test has improved soundness, which is the main source of our improved soundness. Using this test involves several complications, most significantly that projection to affine lines does not preserve individual degrees, and we show how to overcome these difficulties. En route, we extend some existing machinery to more general settings. Specifically, we give proximity generators for Reed-Muller codes, show a more systematic way of handling ``side conditions'' in IOP constructions, and generalize the compiling procedure of [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] to general codes.
• Abstract（参考訳）: IOPP(Interactive Oracle proof of Near of Trivariate Reed-Muller codes)は、いくつかのセキュリティパラメータにおいて、最もよく知られたクエリ複雑性を実現する。 具体的には、次数$d$とセキュリティパラメータ$\lambda\leq \frac{\log^2 d}{\log\log d}$ に対して、私たちの IOPP には、ラウンドバイラウンドのサウンドネス、$O(\lambda)$クエリ、$O(\log\log d)$ラウンド、$O(d)$長さがあります。 これは FRI (Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018) と STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes, which has larger query and round complexity standing at $O(\lambda \log d)$ and $O(\log d+\lambda\log \log d)$ で改善されている。 我々は、同じパラメータを持つNP完全言語 Rank-1-Constraint-Satisfaction の IOP を提供するために、IOPP を使用します。 我々の構成は低音域における線対点検定に基づいている。 軸方向平行試験(すべての先行研究で用いられている)と比較して、一般的なアフィン線試験は音質が向上しており、これは改良された音質の主源である。 このテストはいくつかの合併症を伴うが、最も顕著なことは、アフィン線への投射が個々の度合いを保たないことであり、これらの困難を克服する方法を示す。 途中で、既存の機械をもっと一般的な設定に拡張します。 具体的には、Reed-Muller 符号に近接生成器を与え、IOP 構造において 'side conditions' を扱うより体系的な方法を示し、[Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] のコンパイル手順を一般的な符号に一般化する。

関連論文リスト

• Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis [25.476062424924713]
  本稿では,フィンガープリント方式の下位境界の証明のための一般的なフレームワークを提案する。 宇宙上の任意の適応的数え上げクエリにQ$$$mathcalX$ to accuracy $alpha$ needs $Omega(fracsqrt log|mathcalX| log (1/delta) log Qvarepsilonalpha2)$ sample, matching known upper bounds to constants。
  論文  参考訳（メタデータ） (2024-12-18T23:11:07Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。 我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
  論文  参考訳（メタデータ） (2024-05-08T02:17:10Z)
• The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits [10.329863009504303]
  我々は、$O(fracnDelta2)$の最適なサンプル複雑さを利用するサブ線形メモリを持つストリーミングアルゴリズムは、$Omega(fraclog (1/Delta)log (1/Delta)$ passを必要とすることを示した。 この結果は,[ICML'21] の$O(log(frac1Delta))$-passアルゴリズムと一致し, [ICML'21] は$O(1)$メモリしか使用せず, Assadi と Wang が提案したオープンな質問に答える。
  論文  参考訳（メタデータ） (2023-09-06T16:41:41Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。 このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
  論文  参考訳（メタデータ） (2021-10-07T05:25:23Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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