論文の概要: On the number of solutions to a random instance of the permuted kernel problem

• arxiv url: http://arxiv.org/abs/2406.00453v1
• Date: Sat, 1 Jun 2024 14:31:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 06:55:04.508880
• Title: On the number of solutions to a random instance of the permuted kernel problem
• Title（参考訳）: 置換されたカーネル問題のランダムなインスタンスに対する解の数について
• Authors: Carlo Sanna,
• Abstract要約: 置換カーネル問題(Permuted Kernel Problem、PKP)は、1989年にシャミールによって初めて導入された線型代数の問題である。 我々は、PKPのランダムなインスタンスに対して、期待される解数の正確な公式を提供し、厳密に証明する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Permuted Kernel Problem (PKP) is a problem in linear algebra that was first introduced by Shamir in 1989. Roughly speaking, given an $\ell \times m$ matrix $\mathbf{A}$ and an $m \times 1$ vector $\mathbf{b}$ over a finite field of $q$ elements $\mathbb{F}_q$, the PKP asks to find an $m \times m$ permutation matrix $\mathbf{\pi}$ such that $\mathbf{\pi} \mathbf{b}$ belongs to the kernel of $\mathbf{A}$. In recent years, several post-quantum digital signature schemes whose security can be provably reduced to the hardness of solving random instances of the PKP have been proposed. In this regard, it is important to know the expected number of solutions to a random instance of the PKP in terms of the parameters $q,\ell,m$. Previous works have heuristically estimated the expected number of solutions to be $m! / q^\ell$. We provide, and rigorously prove, exact formulas for the expected number of solutions to a random instance of the PKP and the related Inhomogeneous Permuted Kernel Problem (IPKP), considering two natural ways of generating random instances.
• Abstract（参考訳）: 置換カーネル問題(Permuted Kernel Problem、PKP)は、1989年にシャミールによって初めて導入された線型代数の問題である。 大まかに言えば、$\ell \times m$ matrix $\mathbf{A}$と$m \times 1$ vector $\mathbf{b}$が$q$の元の有限体上のとき、PKP は$m \times m$ permutation matrix $\mathbf{\pi}$ を求める。 近年,PKPのランダムなインスタンスを解くことの難しさに対して,セキュリティを確実に低減できるポスト量子デジタルシグネチャスキームが提案されている。 この点に関して、パラメータ $q,\ell,m$ の観点から、PKP のランダムなインスタンスに対する解の期待数を知ることが重要である。 これまでの研究では、予想されるソリューションの数は$m! q^\ell$。 PKPのランダムなインスタンスと関連する不均一な置換カーネル問題(IPKP)に対して、ランダムなインスタンスを生成する2つの自然な方法を考えることにより、期待される解数の正確な式を、PKPとそれに関連する不均一なパーミューテッドカーネル問題(IPKP)に対して提供し、厳密に証明する。

関連論文リスト

• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Fitting an ellipsoid to a quadratic number of random points [12.519286388088958]
  問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。 任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
  論文  参考訳（メタデータ） (2023-07-03T17:46:23Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Additive estimates of the permanent using Gaussian fields [0.0]
  本稿では,M$M$実行列$A$から加法誤差までの永久性を推定するランダム化アルゴリズムを提案する。 我々は$mathrmperm(A)$を$epsilonbigg(sqrt32Mprod2M_i=1 C_iibigg)$の加算誤差に時間内に見積もることができる。
  論文  参考訳（メタデータ） (2022-12-20T22:13:42Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Multimeasurement Generative Models [7.502947376736449]
  我々は、密度$p_X$ in $mathbbRd$を未知分布からサンプリングする問題を学習とサンプリングの問題を$p_mathbfY$ in $mathbbRMd$とする。
  論文  参考訳（メタデータ） (2021-12-18T02:11:36Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。 また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T14:19: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)
• Probabilistic Iterative Methods for Linear Systems [5.457842083043013]
  我々は、 $mathbbRd$ 上の標準反復法が、確率分布の空間に作用するために、$mathcalP(mathbbRd)$ を解除することを示す。 この論文で提案される反復的手法の出力は、数学P(mathbbRd)$における確率分布の列$mu_mである。
  論文  参考訳（メタデータ） (2020-12-23T11:55:57Z)

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

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