SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

• URL: http://arxiv.org/abs/2609.01469v1
• Date: Tue, 01 Sep 2026 16:04:35 GMT
• Title: SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules
• Abstract summary: We prove that the decision version of the Shortest Vector Problem ($mathrmSVP$) in the $ell binary$-norm is $mathrmNP$-complete on full-rank free sub-counts.<n>The construction also gives $mathrmNP$-hardness of search-$mathrmSVP$ under matrix-time Turing reductions.
• Score: 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.

Related papers

• Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice [1.0152838128195467]
  We show that the $L2$ CVP distance from a random short ring element to the log-unit lattice converges to $frac2sqrt6sqrtn$ as $n=2k-1toinfty$.<n>For the $Linfty$ norm, the maximum over $n$ sub-Gaussian coordinates yields $O(sqrtlog n)$ which translates into a sub-polynomial approximation factor for the Short Generator Problem.
  arXiv  Detail & Related papers  (2026-05-17T12:00:59Z)
• The Algebraic Landscape of Kochen-Specker Sets in Dimension Three [0.0]
  We present a computational survey of Kochen-Specker uncolorability in three-dimensional Hilbert space across two-symbol coordinate alphabets.<n>In every tested alphabet, KS sets arise only when $x$ supports one of two cancellation mechanisms.<n>Two yield potentially new KS graph types.
  arXiv  Detail & Related papers  (2026-03-17T17:31:59Z)
• A Variant of the Bravyi-Terhal Bound for Arbitrary Boundary Conditions [10.560637835517094]
  We consider a quotient $mathbbZD/Lambda$ of $mathbbZD$ of cardinality $n$ on a $D$-dimensional lattice quotient.<n>We prove that if all stabilizer generators act on qubits whose indices lie within a ball of radius $rho$, the minimum distance $d$ of the code satisfies $d leq msqrtgamma_D(sqrtD + 4rho)nfracD-1D$ whenever $n1/D
  arXiv  Detail & Related papers  (2025-02-07T15:18:40Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Synthesis and Arithmetic of Single Qutrit Circuits [0.8192907805418581]
  We study qutrit circuits consisting of words over the Clifford$+D$ cyclotomic gate set.<n>The framework developed to formulate qutrit gate synthesis for Clifford$+D$ extends to qudits of arbitrary prime power.
  arXiv  Detail & Related papers  (2023-11-15T04:50:41Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• SIC-POVMs from Stark units: Prime dimensions n^2+3 [0.41998444721319206]
  We show a recipe for constructing a SIC fiducial vector in complex Hilbert space of dimension of the form $d=n2+3$. Such structures are shown to exist in thirteen prime dimensions of this kind, the highest being $p=19603$.
  arXiv  Detail & Related papers  (2021-12-10T14:05:44Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.