Fugu-MT 論文翻訳(概要): Symmetric Models for Syndrome Decoding

論文の概要: Symmetric Models for Syndrome Decoding

arxiv url: http://arxiv.org/abs/2609.14052v1
Date: Sat, 12 Sep 2026 17:05:09 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-16 07:15:05.647326
Title: Symmetric Models for Syndrome Decoding
Title（参考訳）: シンドローム復号のための対称性モデル
Abstract要約: 本稿では、シンドローム復号問題(SDP)の正確な変種に対する新しいモデルを提案する。我々は、正則度とモデルに関連するイデアルの解度に境界を定め、二項系を解く複雑さを見積もる。
参考スコア（独自算出の注目度）: 2.0871483263418806
License: http://creativecommons.org/licenses/by/4.0/
Abstract: This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our approach to solve other variants of the SDP.
Abstract（参考訳）: 本稿では,2次ケースにおけるシンドローム復号問題(SDP)の正確な変種に対する新しい多項式モデルを提案する。このモデルは基本対称多項式に基づいている。我々は、正則度とモデルに関連するイデアルの解度に境界を定め、対応する多項式系を解く際の計算複雑性を推定する。複雑性の見積もりは、以前の多項式モデルよりも低い。また、SDPの特定のインスタンスに直接依存し、最初のモデルよりも低い複雑さを持つモデルの変種も提供する。最後に、SDPの他の変種を解くために、我々のアプローチを適用する方法について論じる。

関連論文リスト

A Rigorous, Tractable Measure of Model Complexity [12.424687747519037]
本稿では,入力間のモデル間の類似性に基づいて,モデル複雑性の数学的に厳密かつパラメトリックな測度を示す。複雑性の尺度は、カーネル長スケール、隣人数、木数などのモデル固有の複雑性尺度を一般化することを証明する。我々はまた、ランダムな特徴、ランダムな森林、ニューラルネットワーク、勾配の上昇に対する二重降下現象に関する新たな洞察を得るために、我々の測定値を利用する。
論文参考訳（メタデータ） (2026-05-20T13:37:38Z)
Inhomogeneous SSH models and the doubling of orthogonal polynomials [0.0]
シーケンスの二重化法を用いてSu-Schrieffer-Heeger(SSH)モデルの解析を行う。このアプローチは、モデルの分析スペクトルと正確な固有状態をもたらす。
論文参考訳（メタデータ） (2025-11-19T15:23:37Z)
Quadratic Modelings of Syndrome Decoding [0.0]
本稿では,2次方程式系に対する有界重みと完全重み付きシンドローム復号問題(SDP)の高度化について述べる。我々は,SDPインスタンスを$mathbbF_q$で方程式系に変換する新しい手法を導入し,それらの多様体の次元を徹底的に検討する。
論文参考訳（メタデータ） (2024-12-06T08:36:02Z)
Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文参考訳（メタデータ） (2024-03-08T18:50:19Z)
Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
文脈決定プロセス(CMDP)は、遷移カーネルと報酬関数がコンテキスト変数によってインデックス付けされた異なるMDPで時間とともに変化できる強化学習のクラスを記述する。 CMDPは、時間とともに変化する環境で多くの現実世界のアプリケーションをモデル化するための重要なフレームワークとして機能する。 CMDPを2つの線形関数近似モデルで検討する: 文脈変化表現とすべての文脈に対する共通線形重み付きモデルIと、すべての文脈に対する共通表現と文脈変化線形重み付きモデルIIである。
論文参考訳（メタデータ） (2024-02-05T03:25:04Z)
Sample Complexity of Kernel-Based Q-Learning [11.32718794195643]
任意に大規模に割引されたMDPにおいて,$epsilon$-optimal Policyを求める非パラメトリックQ-ラーニングアルゴリズムを提案する。我々の知る限りでは、このような一般モデルの下では、有限サンプルの複雑さを示す最初の結果である。
論文参考訳（メタデータ） (2023-02-01T19:46:25Z)
PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
部分的に観察可能な力学系におけるオンライン強化学習(RL)について検討する。我々は、他のよく知られたモデルをキャプチャする表現モデルである予測状態表現(PSR)モデルに焦点を当てる。我々は,サンプル複雑性のスケーリングにおいて,ほぼ最適なポリシを学習可能な,PSRのための新しいモデルベースアルゴリズムを開発した。
論文参考訳（メタデータ） (2022-07-12T17:57:17Z)
Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
論文参考訳（メタデータ） (2021-03-19T16:34:20Z)
Estimation of Switched Markov Polynomial NARX models [75.91002178647165]
非線形自己回帰(NARX)成分を特徴とするハイブリッド力学系のモデル群を同定する。提案手法は, 特定の回帰器を持つ3つの非線形サブモデルからなるSMNARX問題に対して実証される。
論文参考訳（メタデータ） (2020-09-29T15:00:47Z)
Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文参考訳（メタデータ） (2020-02-20T10:50:58Z)

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