論文の概要: Word Linear Complexity of sequences and Local Inversion of maps over finite fields
- arxiv url: http://arxiv.org/abs/2311.06574v1
- Date: Sat, 11 Nov 2023 14:06:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 23:32:03.961440
- Title: Word Linear Complexity of sequences and Local Inversion of maps over finite fields
- Title（参考訳）: 有限体上の列の言葉線形複素性と写像の局所反転
- Authors: Virendra Sule,
- Abstract要約: 本稿では、有限体上のベクトル値列の概念を、そのアンサンブルの線形複素性$の拡張として展開する。
行列極小は、列が周期的であるとき、一意の局所逆の$x$ in $ffn$を解くために与えられた$ffn$ in $ffn$において、写像$F:ffnが反復的に生成したベクトルで使用できることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper develops the notion of \emph{Word Linear Complexity} ($WLC$) of vector valued sequences over finite fields $\ff$ as an extension of Linear Complexity ($LC$) of sequences and their ensembles. This notion of complexity extends the concept of the minimal polynomial of an ensemble (vector valued) sequence to that of a matrix minimal polynomial and shows that the matrix minimal polynomial can be used with iteratively generated vector valued sequences by maps $F:\ff^n\rightarrow\ff^n$ at a given $y$ in $\ff^n$ for solving the unique local inverse $x$ of the equation $y=F(x)$ when the sequence is periodic. The idea of solving a local inverse of a map in finite fields when the iterative sequence is periodic and its application to various problems of Cryptanalysis is developed in previous papers \cite{sule322, sule521, sule722,suleCAM22} using the well known notion of $LC$ of sequences. $LC$ is the degree of the associated minimal polynomial of the sequence. The generalization of $LC$ to $WLC$ considers vector valued (or word oriented) sequences such that the word oriented recurrence relation is obtained by matrix vector multiplication instead of scalar multiplication as considered in the definition of $LC$. Hence the associated minimal polynomial is matrix valued whose degree is called $WLC$. A condition is derived when a nontrivial matrix polynomial associated with the word oriented recurrence relation exists when the sequence is periodic. It is shown that when the matrix minimal polynomial exists $n(WLC)=LC$. Finally it is shown that the local inversion problem is solved using the matrix minimal polynomial when such a polynomail exists hence leads to a word oriented approach to local inversion.
- Abstract（参考訳）: 本稿では、有限体上のベクトル値列の「emph{Word Linear Complexity}」(WLC$)の概念を、列とそのアンサンブルの拡張として展開する。
この複雑性の概念は、アンサンブル(ベクトル値)列の最小多項式の概念を行列最小多項式の最小多項式に拡張し、行列最小多項式が周期型であるときの方程式のユニークな局所的逆$x$を解くために与えられた$y$ in $\ff^n$において、写像$F:\ff^n\rightarrow\ff^n$で反復的に生成されたベクトル値列で使用できることを示す。
反復列が周期的であるときの有限体における写像の局所的逆問題とそのクリプトアナリシスの様々な問題への応用のアイデアは、よく知られた$LC$という概念を用いて、以前の論文 \cite{sule322, sule521, sule722,suleCAM22} で展開されている。
$LC$ は、関連する列の最小多項式の次数である。
$LC$ から $WLC$ への一般化は、ワード指向の反復関係が $LC$ の定義で考慮されるスカラー乗法の代わりに行列ベクトル乗法によって得られるようなベクトル値(または単語指向)列を考える。
したがって、関連する最小多項式は、次数が$WLC$と呼ばれる行列値である。
単語指向反復関係に関連する非自明な行列多項式が周期的であるときに条件が導出される。
行列最小多項式が存在するとき、$n(WLC)=LC$である。
最後に、そのようなポリノメールが存在する場合、行列最小多項式を用いて局所反転問題を解くことにより、局所反転に対する単語指向のアプローチが導かれることを示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
我々は、このマルコフ連鎖のほぼ最適な実装を示し、ステップごとの複雑さは、約$A$のゼロでないエントリの数であるのに対して、マルコフ連鎖のステップの数は同じである。
1) このダイキンウォークで生じる行列はゆっくりと変化すること,2) この遅い変化を利用した効率的な線形解法を展開し, 以前のステップで計算した情報を用いて行列の逆転を高速化すること,3) ランダム化されたテイラー級数に基づく推定器を用いてメトロポリスフィルタステップにおける行列項の計算を高速化すること,である。
論文 参考訳（メタデータ） (2024-09-06T14:49:43Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Polynomial Complexity of Inversion of sequences and Local Inversion of Maps [0.0]
論文は、二項体上の有限列のエンプインバージョン問題に対する解を定義し、探求する。
RR を定義する固定次数の複素数の最小数(位数)は、その次数の列の EmphPolynomial と呼ばれる。
論文 参考訳（メタデータ） (2024-06-28T02:34:29Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products [9.661328973620531]
自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。
我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。
我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
論文 参考訳（メタデータ） (2023-11-03T14:56:24Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Spectrum of inner-product kernel matrices in the polynomial regime and
multiple descent phenomenon in kernel ridge regression [3.997680012976965]
カーネル行列はその次数-$ell$近似によってよく近似される。
行列のスペクトルが分布に収束することを示す。
論文 参考訳（メタデータ） (2022-04-21T22:20:52Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Learning sums of powers of low-degree polynomials in the non-degenerate
case [2.6109033135086777]
我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。
本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
論文 参考訳（メタデータ） (2020-04-15T06:18:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。