論文の概要: The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences
- arxiv url: http://arxiv.org/abs/2404.03530v2
- Date: Wed, 3 Jul 2024 16:03:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-04 19:44:31.448111
- Title: The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences
- Title（参考訳）: アフィン半正則多項式列のグレーブナー基底を計算する解次数
- Authors: Momonari Kudo, Kazuhiro Yokoyama,
- Abstract要約: 本研究では,アフィン半正則配列の解度とその均質化配列について検討する。
これらの結果は,Gr"オブザーバー基底の計算方法の正確性に関する数学的に厳密な証明を与えると考えられる。
- 参考スコア（独自算出の注目度）: 0.9208007322096533
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Determining the complexity of computing Gr\"{o}bner bases is an important problem both in theory and in practice, and for that the solving degree plays a key role. In this paper, we study the solving degrees of affine semi-regular sequences and their homogenized sequences. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gr\"{o}bner bases of the ideal generated by an affine semi-regular sequence. This paper is a sequel of the authors' previous work and gives additional results on the solving degrees and important behaviors of Gr\"obner basis computation. We also define the generalized degree of regularity for a sequence of homogeneous polynomials. For the homogenization of an affine semi-regular sequence, we relate its generalized degree of regularity with its maximal Gr\"{o}bner basis degree (i.e., the solving degree of the homogenized sequence). The definition of a generalized (cryptographic) semi-regular sequence is also given, and it derives a new cryptographic assumption to estimate the security of cryptosystems and signature schemes. From our experimental observation, we raise a conjecture and some questions related to this generalized semi-regularity. These new definitions and our results provide a theoretical formulation of (somehow heuristic) discussions done so far in the cryptographic community.
- Abstract（参考訳）: Gr\"{o}bner 基底の計算の複雑さを決定することは、理論と実際の両方において重要な問題であり、解度が重要な役割を果たす。
本稿では,アフィン半規則配列とその同種配列の解度について検討する。
いくつかの結果は、アフィン半正則列によって生成されるイデアルのGr\"{o}bner基底を計算する方法の正しさの数学的に厳密な証明を与えると考えられる。
本論文は,著者の過去の研究の続編であり,Gr\の解度と重要な挙動に関する追加的な結果を与える。
また、同次多項式列に対する一般化された正則性の次数も定義する。
アフィン半正則列の均質化については、その一般化された正則性の次数と最大 Gr\"{o}bner 基底次数(すなわち、同質化列の解度)を関連付ける。
一般化された(暗号的な)半規則シーケンスの定義も与えられ、暗号システムとシグネチャスキームのセキュリティを見積もる新たな暗号仮定が導かれる。
実験的な観察から、この一般化された半正則性に関する予想といくつかの疑問を提起する。
これらの新たな定義とその結果は、これまで暗号コミュニティで行われてきた(幾らかヒューリスティックな)議論を理論的に定式化したものです。
関連論文リスト
- Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry [63.694184882697435]
グローバル共分散プーリング(GCP)は、高レベルの表現の2階統計を利用して、ディープニューラルネットワーク(DNN)の性能を向上させることが実証されている。
論文 参考訳（メタデータ） (2024-07-15T07:11:44Z) - Constructing structured tensor priors for Bayesian inverse problems [6.191418251390628]
我々は、解が構造テンソルであるという信念を符号化するガウス先行を特徴づける。
本稿では,新しいカーネル関数を設計し,効率的に計算する方法を示す。
すべてのアプリケーションはJuliaのリアクティブPlutoノートブックとして実装されている。
論文 参考訳（メタデータ） (2024-06-25T14:40:34Z) - Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - Solving Degree Bounds For Iterated Polynomial Systems [0.0]
我々は,MIMC,Feistel-MiMC,Feistel-MiMC-Hash,Hades,GMiMCに対する攻撃に対する正則性評価を行った。
我々の境界は、これらの設計に対するGr"オブナーベースアタックの仮定された複雑さと一致している。
論文 参考訳（メタデータ） (2023-10-05T16:10:14Z) - Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
種々の非重み付きグラフの集合上でガウス過程の先行を定義するための原理的手法を提案する。
さらに、未重み付きグラフの同値類の集合を検討し、それに対する事前の適切なバージョンを定義する。
化学の応用に触発されて、我々は、小データ構造における実際の分子特性予測タスクについて、提案手法を解説した。
論文 参考訳（メタデータ） (2022-11-03T10:18:17Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Regularization of Persistent Homology Gradient Computation [8.7314407902481]
本稿では,グループ化項の追加による永続的ホモロジー計算の正規化手法を提案する。
これは、勾配が個々の点ではなくより大きな実体に対して定義されることを保証するのに役立つ効果がある。
論文 参考訳（メタデータ） (2020-11-11T14:16:33Z) - The semiring of dichotomies and asymptotic relative submajorization [0.0]
我々は、事前順序付き半環上のストラッセンの定理の一般化を用いて、量子二コトミーと非対称微分可能性の資源理論を研究する。
非正規化ジコトミー上で定義される相対的部分行列化の変種は、テンソル積の下で乗法的であり、直和の下で加法的である実数値モノトンによって特徴づけられる。
論文 参考訳（メタデータ） (2020-04-22T14:13:26Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。