論文の概要: Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem

• arxiv url: http://arxiv.org/abs/2504.01230v1
• Date: Tue, 01 Apr 2025 22:39:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-03 13:17:42.945916
• Title: Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem
• Title（参考訳）: ハイウェイ・トゥ・ハル:一般行列符号等価問題の解法
• Authors: Alain Couvreur, Christophe Levrat,
• Abstract要約: 行列符号同値問題は、2つの行列空間 $mathcalC,mathcalDsubset mathbbF_qmtimes n$ of dimension $k$ で与えられる。 本稿では,一般の場合の問題を解くアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.450536872346658
• License:
• Abstract: The matrix code equivalence problem consists, given two matrix spaces $\mathcal{C},\mathcal{D}\subset \mathbb{F}_q^{m\times n}$ of dimension $k$, in finding invertible matrices $P\in\mathrm{GL}_m(\mathbb{F}_q)$ and $Q\in\mathrm{GL}_n(\mathbb{F}_q)$ such that $\mathcal{D}=P\mathcal{C} Q^{-1}$. Recent signature schemes such as MEDS and ALTEQ relate their security to the hardness of this problem. Naranayan et. al. recently published an algorithm solving this problem in the case $k = n =m$ in $\widetilde{O}(q^{\frac k 2})$ operations. We present a different algorithm which solves the problem in the general case. Our approach consists in reducing the problem to the matrix code conjugacy problem, i.e. the case $P=Q$. For the latter problem, similarly to the permutation code equivalence problem in Hamming metric, a natural invariant based on the Hull of the code can be used. Next, the equivalence of codes can be deduced using a usual list collision argument. For $k=m=n$, our algorithm achieves the same complexity as in the aforementioned reference. However, it extends to a much broader range of parameters.
• Abstract（参考訳）: 2つの行列空間 $\mathcal{C},\mathcal{D}\subset \mathbb{F}_q^{m\times n}$ of dimension $k$, in find in find invertible matrices $P\in\mathrm{GL}_m(\mathbb{F}_q)$ and $Q\in\mathrm{GL}_n(\mathbb{F}_q)$ that $\mathcal{D}=P\mathcal{C} Q^{-1}$ である。 最近のMEDSやALTEQのようなシグネチャスキームは、それらのセキュリティとこの問題の難しさを関連づけている。 ナラナヤンらは最近、この問題を$k = n = m$ in $\widetilde{O}(q^{\frac k 2})$演算で解くアルゴリズムを公表した。 本稿では,一般の場合の問題を解くアルゴリズムを提案する。 提案手法は,行列コード共役問題,すなわち$P=Q$という問題に問題を還元する。 後者の問題では、ハミング計量の置換符号同値問題と同様に、符号のハルに基づく自然な不変量を用いることができる。 次に、通常のリスト衝突引数を用いて符号の等価性を推定することができる。 k=m=n$の場合、上記の参照と同じ複雑さを達成する。 しかし、より広い範囲のパラメータに拡張される。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Structured Semidefinite Programming for Recovering Structured Preconditioners [41.28701750733703]
  正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。 我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
  論文  参考訳（メタデータ） (2023-10-27T16:54:29Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。 本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
  論文  参考訳（メタデータ） (2023-03-22T04:07:26Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。 また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T14:19:43Z)
• Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
  行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。 任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。 同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
  論文  参考訳（メタデータ） (2020-12-11T17:36:33Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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