Fugu-MT 論文翻訳(概要): Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings

論文の概要: Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings

arxiv url: http://arxiv.org/abs/2112.05023v2
Date: Tue, 7 May 2024 07:24:37 GMT
ステータス: 処理完了
システム内更新日: 2024-05-08 20:52:38.083948
Title: Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings
Title（参考訳）: 多項式XL: 多項式環上のマクロ行列を用いたXLアルゴリズムの変数
Authors: Hiroki Furue, Momonari Kudo,
Abstract要約: 我々は h-XL の変種を示し、これをイポリノミアル XL (PXL) と呼ぶ。 k$変数を推測する前に、環上のマコーレー行列の列を除去することにより、各推定値に必要な演算量をh-XLと比較することができる。 PXLを解析した結果、PXLは$n=m$のランダムシステム理論において、他のアルゴリズムよりも効率的であることが示唆された。
参考スコア（独自算出の注目度）: 0.46040036610482665
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Solving a system of $m$ multivariate quadratic equations in $n$ variables over finite fields (the MQ problem) is one of the important problems in the theory of computer science. The XL algorithm (XL for short) is a major approach for solving the MQ problem with linearization over a coefficient field. Furthermore, the hybrid approach with XL (h-XL) is a variant of XL guessing some variables beforehand. In this paper, we present a variant of h-XL, which we call the \textit{polynomial XL (PXL)}. In PXL, the whole $n$ variables are divided into $k$ variables to be fixed and the remaining $n-k$ variables as ``main variables'', and we generate a Macaulay matrix with respect to the $n-k$ main variables over a polynomial ring of the $k$ (sub-)variables. By eliminating some columns of the Macaulay matrix over the polynomial ring before guessing $k$ variables, the amount of operations required for each guessed value can be reduced compared with h-XL. Our complexity analysis of PXL (under some practical assumptions and heuristics) gives a new theoretical bound, and it indicates that PXL could be more efficient than other algorithms in theory on the random system with $n=m$, which is the case of general multivariate signatures. For example, on systems over the finite field with ${2^8}$ elements with $n=m=80$, the numbers of operations deduced from the theoretical bounds of the hybrid approaches with XL and Wiedemann XL, Crossbred, and PXL with optimal $k$ are estimated as $2^{252}$, $2^{234}$, $2^{237}$, and $2^{220}$, respectively.
Abstract（参考訳）: 有限体上の$n$変数における$m$2次方程式系の解法(MQ問題)は、計算機科学理論における重要な問題の1つである。 XLアルゴリズム(略してXL)は、係数場上の線形化でMQ問題を解くための主要なアプローチである。さらに、XL (h-XL) とのハイブリッドアプローチは、予めいくつかの変数を推測する XL の変種である。本稿では、h-XL の変種について述べ、これを \textit{polynomial XL (PXL)} と呼ぶ。 PXL では、$n$変数全体を$k$変数に分割し、残りの$n-k$変数を ``main variables'' とし、$k$ (sub-)変数の多項式環上の $n-k$主変数に関して Macaulay 行列を生成する。 k$変数を推測する前に多項式環上のマコーレー行列の列を除去することにより、各推定値に必要な演算量をh-XLと比較することができる。我々のPXLの複雑性解析(いくつかの実践的な仮定とヒューリスティックスの下で)は、新しい理論的境界を与え、PXLは、一般的な多変量シグネチャである$n=m$の理論上の他のアルゴリズムよりも効率的であることを示す。例えば、${2^8}$元が$n=m=80$の有限体上のシステムでは、XL と Wiedemann XL、Crossbred、PXL とのハイブリッドアプローチの理論的境界から導出される演算の数は、それぞれ 2^{252}$、 2^{234}$、 2^{237}$、 2^{220}$と推定される。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers [0.0]
我々はPsi-HHLが$mathcalkappa$行列を含む状況に対処できることを実証する。行列は最大で256倍256$で、mathcalkappa$は約466である。
論文参考訳（メタデータ） (2024-07-31T14:41:30Z)
Lifted Inference with Linear Order Axiom [0.0]
We consider the task of weighted first-order model counting (WFOMC) 我々は、少なくとも2つの論理変数を持つ論理文の WFOMC が $n$ の時間で実行可能であることを示す。線形順序でWFOMCをn$で計算できる新しい動的プログラミングベースアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-11-02T14:38:01Z)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文参考訳（メタデータ） (2022-09-04T10:01:39Z)
Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
論文参考訳（メタデータ） (2022-02-11T23:53:43Z)
Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文参考訳（メタデータ） (2021-01-29T18:57:52Z)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文参考訳（メタデータ） (2020-12-14T18:14:08Z)
FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。当社のメソッドは、最大50,000ドルという問題でテストしています。
論文参考訳（メタデータ） (2020-06-15T21:55:34Z)
Learning Polynomials of Few Relevant Dimensions [12.122488725065388]
多項式回帰は学習と統計の基本的な原始である。およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
論文参考訳（メタデータ） (2020-04-28T18:00:18Z)
Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
論文参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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