論文の概要: SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

• arxiv url: http://arxiv.org/abs/2609.01469v1
• Date: Tue, 01 Sep 2026 16:04:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-02 16:31:36.83014
• Title: SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules
• Title（参考訳）: SVPがNP-Hard for some Rank-2 Cyclotomic Modulesを発表
• Authors: Jiaqi Liu, Yansong Feng, Yanbin Pan,
• Abstract要約: 我々は、$ell binary$-normにおける最短ベクトル問題(mathrmSVP$)の決定バージョンが、フルランクのフリーサブカウントで$mathrmNP$-completeであることを証明する。 この構成はまた、行列時間チューリング還元の下で、$mathrmNP$-hardness of search-$mathrmSVP$を与える。
• 参考スコア（独自算出の注目度）: 17.893655677334575
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Let $q$ range over primes congruent to $3$ modulo $4$. Let $ζ_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(ζ_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[ζ_q]$. We prove that the decision version of the Shortest Vector Problem ($\mathrm{SVP}$) in the $\ell_2$-norm is $\mathrm{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. As a $\mathbb{Z}$-lattice, the module has rank $2(q-1)$, which grows with $q$. The main obstacle is closure under the action of $\mathcal{O}_K$. A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of $\mathcal{O}_K$, and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett--Peikert Reed--Solomon lattice to a principal cyclotomic ideal and use Wan's point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, a checker based on a quadratic Gauss sum turns the X3C equations into a canonical squared norm. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out every unintended vector created by the $\mathcal{O}_K$-action. Each constructed instance consists of a prime $q\equiv3\pmod4$, two integral generators whose $2\times2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathrm{NP}$-hardness of search-$\mathrm{SVP}$ under polynomial-time Turing reductions.
• Abstract（参考訳）: 素数に対する$q$の範囲を$$3$modulo $$とする。 1 の原始 $q$th 根とし、整数環 $\mathcal{O}_K=\mathbb{Z}[\_q]$ とする。 我々は、$\ell_2$-norm in the $\ell_2$-norm is $\mathrm{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C)。 モジュールのランクは2で固定されます。 $\mathbb{Z}$-lattice として、加群は階数 2(q-1)$ を持ち、$q$ で成長する。 主な障害は$\mathcal{O}_K$の作用によるクロージャである。 非零ベクトルを含む加群はまた、そのベクトルのすべてのスカラー倍を$\mathcal{O}_K$のゼロでない元で含む。 3つの考えがこの障害を克服する。 まず、ベネット・ピーカルト・リード-ソロモン格子を主シクロトミックイデアルに写像し、ワンの点数推定を用いて、このイデアルの余集合が多くの二項係数代表を含むことを証明する。 第二に、二次ガウス和に基づくチェッカーは、X3C方程式を正準二乗ノルムに変換する。 第3に、チェッカーと第2の加群座標は、イデアルコセットに対する分離境界と組み合わせて、$\mathcal{O}_K$-アクションによって生成されるすべての意図しないベクトルを除外する。 構成された各インスタンスは、素の$q\equiv3\pmod4$と、2.$\times2$のジェネレータが非ゼロ行列を持つ2つの積分生成器と、整数二乗しきい値からなる。 この構成はまた、多項式時間チューリング還元の下で、$\mathrm{NP}$-hardness of search-$\mathrm{SVP}$を与える。

関連論文リスト

• A Variant of the Bravyi-Terhal Bound for Arbitrary Boundary Conditions [10.560637835517094]
  商 $mathbbZD/Lambda$ of $mathbbZD$ of cardinality $n$ on a $D$-dimensional lattice quotient を考える。 すべての安定化器ジェネレータが半径$rho$の範囲内にある量子ビットに作用すると、コードの最小距離$d$は$d leq msqrtgamma_D(sqrtD + 4rho)nfracD-1D$である。
  論文  参考訳（メタデータ） (2025-02-07T15:18:40Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
  論文  参考訳（メタデータ） (2024-11-21T17:41:09Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Synthesis and Arithmetic of Single Qutrit Circuits [0.8192907805418581]
  本稿では,Clifford$+D$サイクロトミックゲート集合上の単語からなるクォート回路について検討する。 このフレームワークは、任意の素数の四重項に拡張するクリフォード$+D$の四重項ゲート合成を定式化するために開発された。
  論文  参考訳（メタデータ） (2023-11-15T04:50:41Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)

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

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