論文の概要: Computation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem

• arxiv url: http://arxiv.org/abs/2502.12721v1
• Date: Tue, 18 Feb 2025 10:38:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:05:09.926028
• Title: Computation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem
• Title（参考訳）: MinRank問題支援マイナーモデリングのためのヒルベルト級数計算
• Authors: Magali Bardet, Alban Gilard,
• Abstract要約: 我々は、ジェネリックインスタンスに対するサポートマイナーモデリングの完全なヒルベルト級数の公式と証明を提供する。 次に、このイデアルは、変数の行列のすべての部分集合の集合の部分集合によって生成されることを示す。 我々は,Mirathシグネチャスキームのパラメータに対して,MinRankインスタンスを解く複雑さを推定する。
• 参考スコア（独自算出の注目度）: 0.19731444261635428
• License:
• Abstract: The MinRank problem is a simple linear algebra problem: given matrices with coefficients in a field, find a non trivial linear combination of the matrices that has a small rank. There are several algebraic modeling of the problem. The main ones are: the Kipnis-Shamir modeling, the Minors modeling and the Support-Minors modeling. The Minors modeling has been studied by Faug\`ere et al. in 2010, where the authors provide an analysis of the complexity of computing a Gr\"obner basis of the modeling, through the computation of the exact Hilbert Series for a generic instance. For the Support-Minors modeling, the first terms of the Hilbert Series are given by Bardet et al. in 2020 based on an heuristic and experimental work. In this work, we provide a formula and a proof for the complete Hilbert Series of the Support Minors modeling for generic instances. This is done by adapting well known results on determinantal ideals to an ideal generated by a particular subset of the set of all minors of a matrix of variables. We then show that this ideal is generated by a particular subset of the set of all minors of a matrix of variables. We then show that this ideal is generated by standard monomials having a particular shape, and derive the Hilbert Series by counting the number of such standard monomials. Following the work done for the Minors Modeling, we then transfer the properties of this particular determinantal ideal to ideals generated by the Support Minors system, by adding generic forms. This work allows to make a precise comparison between the Minors and Support Minors modeling, and a precise estimate of the complexity of solving MinRank instances for the parameters of the Mirath signature scheme that is currently at the second round of the NIST standardization process for Additional Digital Signature Schemes.
• Abstract（参考訳）: MinRank問題(英語版)は単純線型代数問題である: 体に係数を持つ行列が与えられたとき、小さな階数を持つ行列の非自明な線型結合を見つける。 この問題の代数的モデリングはいくつかある。 主なものは、Kipnis-Shamirモデリング、Minorsモデリング、Support-Minorsモデリングである。 2010年にFaug\`ere et alによって研究され、著者らはジェネリック・インスタンスに対する正確なヒルベルト・シリーズの計算を通して、モデリングのGr\"オブナーベースを計算することの複雑さの分析を行っている。 サポート・マイナーズ・モデリングでは、ヒルベルト・シリーズの最初の用語は、ヒューリスティックで実験的な研究に基づいて、バルデットらによって2020年に与えられる。 本研究では、ジェネリック・インスタンスに対するサポート・マイナーズ・モデリングの完全なヒルベルト・シリーズの式と証明を提供する。 これは、決定的イデアルに関するよく知られた結果を、変数の行列のすべての部分集合の特定の部分集合によって生成されるイデアルに適応させることによって達成される。 次に、このイデアルは、変数の行列のすべての部分集合の特定の部分集合によって生成されることを示す。 すると、このイデアルは特定の形状の標準単項によって生成され、そのような標準単項の数を数えてヒルベルト級数(英語版)を導出することを示す。 この決定的イデアルの特性を、Support Minorsシステムによって生成されたイデアルに、ジェネリックフォームを追加して転送する。 この研究により、マイナーズとサポートマイナーズモデリングの正確な比較を可能にし、Mirathシグネチャスキームのパラメータに対するMinRankインスタンスの解決の複雑さを正確に見積もることができる。

関連論文リスト

• Irreducible matrix representations for the walled Brauer algebra [0.9374652839580183]
  本稿では、部分転置置換作用素の代数の表現論、$mathcalAd_p,p$について考察する。 これは抽象壁付きブラウアー代数に対する行列表現を提供する。 この代数学は近年、量子情報理論の関連性から大きな注目を集めている。
  論文  参考訳（メタデータ） (2025-01-22T18:22:20Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• A novel sampler for Gauss-Hermite determinantal point processes with application to Monte Carlo integration [0.0]
  我々は、$mathbbRd$上の新しい決定点プロセスが実際にどのようにサンプリングされ、モンテカルロ積分を改善するために使用されるかを示す。 この新過程のサンプルはガウス測度に対するモンテカルロ積分において有用であることが示されている。
  論文  参考訳（メタデータ） (2022-03-15T16:54:03Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。 言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
  論文  参考訳（メタデータ） (2022-01-08T00:47:50Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  本稿ではランダム行列理論の手法を用いて、単純な線形回帰に対して理想的なトレーニング-テストデータ分割を求める。 それは「理想」を整合性計量を満たすものとして定義し、すなわち経験的モデル誤差は実際の測定ノイズである。 本論文は,任意のモデルのトレーニングとテストサイズを,真に最適な方法で解決した最初の論文である。
  論文  参考訳（メタデータ） (2021-12-11T13:18:33Z)
• Sparse Universum Quadratic Surface Support Vector Machine Models for Binary Classification [0.0]
  カーネルフリーな2次曲面サポートベクターマシンモデルを設計する。 二次曲面のヘシアンにおける潜在的空間パターンの検出に有用であるL1ノルム正規化版を提案する。 提案モデルの実現可能性と有効性を示すために、人工的および公共のベンチマークデータセットの数値実験を実施します。
  論文  参考訳（メタデータ） (2021-04-03T07:40:30Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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