論文の概要: Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem
- arxiv url: http://arxiv.org/abs/2504.01230v2
- Date: Fri, 06 Jun 2025 12:48:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-09 17:28:42.917227
- Title: Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem
- Title（参考訳）: ハイウェイ・トゥ・ハル:一般行列符号等価問題の解法
- Authors: Alain Couvreur, Christophe Levrat,
- Abstract要約: 本稿では,一般の場合の行列符号等価問題を解く新しいアルゴリズムを提案する。
我々のアルゴリズムは、ナラヤナンのエフェットal.と同じ時間複雑さを達成できるが、空間の複雑さは低い。
- 参考スコア（独自算出の注目度）: 4.450536872346658
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- 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. Recent works by Narayanan, Qiao and Tang on the one hand and by Ran and Samardjiska on the other hand tackle this problem. The former is restricted to the ``cubic'' case $k = m =n$ and succeeds in $\widetilde{\mathcal{O}}(q^{\frac k 2})$ operations. The latter is an algebraic attack on the general problem whose complexity is not fully understood and which succeeds only on $\mathcal{O}(1/q)$ instances. We present a novel algorithm which solves the problem in the general case. Our approach consists in reducing the problem to the matrix code conjugacy problem, \emph{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 \emph{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 time complexity as Narayanan \emph{et al.} but with a lower space complexity. Moreover, ours 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のようなシグネチャスキームは、それらのセキュリティとこの問題の難しさを関連づけている。
近年の奈良柳庵・清王・唐による作品や、蘭・サマルジスカによる作品もこの問題に対処している。
前者は `cubic'' の場合 $k = m =n$ に制限され、$\widetilde{\mathcal{O}}(q^{\frac k 2})$ 演算で成功する。
後者は、複雑性が完全には理解されておらず、$\mathcal{O}(1/q)$インスタンスでのみ成功する一般問題に対する代数的攻撃である。
本稿では,一般の場合の問題を解く新しいアルゴリズムを提案する。
提案手法は, 行列符号共役問題, \emph{i.e.} に対する問題を$P=Q$とする。
後者の問題については、ハミング計量の置換符号同値問題と同様に、符号の \emph{Hull} に基づく自然な不変量を用いることができる。
次に、通常のリスト衝突引数を用いて符号の等価性を推定することができる。
k=m=n$ の場合、我々のアルゴリズムはNarayanan \emph{et al } と同じ時間複雑さを達成できるが、空間の複雑さは低い。
さらに、より広い範囲のパラメータまで拡張しています。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。