論文の概要: Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One

• arxiv url: http://arxiv.org/abs/2610.34404v1
• Date: Sun, 25 Oct 2026 16:06:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:13.609829
• Title: Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One
• Title（参考訳）: ガビデュリン符号の最大符号復号は次元1でもNPハードである
• Abstract要約: k = 1 であっても、ガビデュリン符号の最大様復号化は NP-hard であることが証明できる。 減少は決定論的であり、その結果、Fqmのランクシンドローム復号(RSD)とランク最小距離(RMD)はNP完全である。
• 参考スコア（独自算出の注目度）: 4.184419714263417
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fix a prime power q. We prove that deciding whether a received word y in Fnqm lies at rank distance at most n-2 from the one-dimensional Gabidulin code {{λ.g : λ in Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami-Vardy theorem for Reed-Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami-Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq-subspaces U, W in FqN , decide whether some non-zero a in U satisfies a^(q+1) in W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq-linear map and decoding at radius n - 2 as the search for an Fq-plane on which it acts as a scalar. With support U + τ W in a cubic extension and map a + τ b to a^(q^2) + τ bq^q , two Frobenius twists force solution planes to encode the relation a^(q+1) in W . All constructions are explicit and polynomial, with N = O(qd^2 ), n less than N + d, and m = 3N .
• Abstract（参考訳）: 素数 q を固定する。 Fnqm の受信語 y が 1 次元ガビデュリン符号 {{λ} から少なくとも n-2 のランク距離にあるかどうかを判定する。 g : λ in Fqm } は NP 完全である。 したがって、ガビデュリン符号の最大様復号は k = 1 であっても NP-ハードであり、リード・ソロモン符号のグラスワミ・ヴァーディ定理の類似である。 対照的にハミング計量では、この半径の硬さは、グルースワミ・ヴァーディの定理のように、長さとともに成長する次元を必要とする。 その結果、Fqm-linear符号のランクシンドローム復号(RSD)とランク最小距離(RMD)は、決定論的多項式還元の下でNP完全である。 Fq-部分空間 U, W in FqN が与えられたとき、U 内の非零 a が W 内の a^(q+1) を満たすかどうかを決定する。 d 個の未知の二次系は TSM に符号化され、次に TSM は Gabidulin の復号に符号化される。 最後のステップは、受信した単語をFq-線型写像とみなし、半径 n - 2 での復号を、スカラーとして機能するFq-平面の探索とみなす。 立方体拡大における U + τ W のサポートと a + τ b を a^(q^2) + τ bq^q に写像すると、2つのフロベニウスは W 内の関係 a^(q+1) を符号化するために、解平面を強制的にねじる。 すべての構成は明示的で多項式であり、N = O(qd^2 )、n は N + d 未満、m = 3N である。

関連論文リスト

• Singer-Difference-Set Qudit Stabilizer Codes from Non-Degenerate Quadrics in PG(d,q)PG(d,q): Construction, Structural Theorems, and Monte-Carlo Performance [47.54490246947129]
  素数 q と次元 d >= 2 の q 論理型非CSS キュート安定化符号の族 Q(q,d) を提案する。 1.5 x 106 でのモンテカルロ試験では、Q(5,2) はステアーンよりも70倍に改善されている。
  論文  参考訳（メタデータ） (2026-10-01T19:17:44Z)
• Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry [6.7936678022428225]
  最適多項式補間問題(OPI)は、できるだけ多くの与えられた入力に対して所定の部分集合に値を持つ有限体上の低次を求める。 副生成物として、特定のパラメータ状態における太陽とウーターの存在境界も改善する。 我々の結果は、任意の距離分離可能符号(MDS)に関してMax-LINSAT問題に拡張される。
  論文  参考訳（メタデータ） (2026-07-16T07:18:57Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Algebraic Geometry Codes and Decoded Quantum Interferometry [0.0]
  Decoded Quantum Interferometry (DQI) は、デコード問題と最適化問題をペア化する双対性を定義する。 HOPIはHermitian曲線上の回帰問題であり、Hermitian符号の双対はHermitian符号であるので、HOPI問題はHermitian符号の近似リスト復元と見なすこともできる。
  論文  参考訳（メタデータ） (2025-10-08T03:25:30Z)
• Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices [19.216283072982005]
  スパースベクトルを見つけることは、コード、部分空間、格子を含むいくつかの文脈で生じる根本的な問題である。 我々は、PCP定理をバイパスする新しいアプローチを用いて、これらの変種すべてに対して強い不適合性を証明した。 我々の主な結果は、任意の定数係数内の実部分空間における最も広いベクトルを近似することがNPハードであることである。
  論文  参考訳（メタデータ） (2024-10-03T16:22:07Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• 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)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)

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

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