CS Paper Radar

Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time

Yichuan Cao, Xiao-Shan Gao, Qiao-Long Huang, Jiawei Nie

cs.CC ·submitted 2026-10-27 13:04 UTC · v1
theory

Abstract

In this paper, we prove that irreducibility testing for sparse polynomials in $\mathbb{Z}[X]$ is coNP-hard under deterministic polynomial-time many-one reductions. That is, there exists no polynomial-time irreducibility test algorithm unless $\mathrm P=\mathrm{NP}$. We also provide an upper bound for this problem by demonstrating that the same irreducibility testing problem lies in $\mathsf{PP}\subseteq\mathsf{PSPACE}$; in other words, it can be solved in probabilistic polynomial time and, moreover, within polynomial space. The fact that $\mathsf{SparseIrred}_{\mathbb{Z}}\in\mathsf{PP}$ relies on the quasi-Riemann hypothesis result of Cureton--Thorner and on the uniform effective prime-ideal bound by Frei--Sofos--Widmer just posted recently.

Closest papers

Nearest neighbours by meaning across the whole index.

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

cs.CC ·2026-11-05 ·Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin
theory similarity 0.68
Abstract

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

0.23

Euclidean SVP is NP-hard for Cyclic Lattices

cs.CC ·2026-09-15 ·Daqing Wan
theory similarity 0.65
Abstract · 39 pages

We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.

0.38

Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

cs.CC math.NT ·2026-11-01 ·Joseph M. Shunia
theory similarity 0.64
Abstract · 12 pages. An earlier version appeared as Revision 2 of ECCC TR23-200: https://eccc.weizmann.ac.il/report/2023/200/#revision2

We give a deterministic polynomial-time primality test whose main verification is the congruence $(1+X)^n=1+X^n$ in $C_n[X]/(X^r-b(Y))$, where $C_n=(\mathbb{Z}/n\mathbb{Z})[Y]/(Φ_r(Y))$. Two identities in the coefficient ring normalize $b$ and ensure compatibility with the main congruence. A finite-field root count and a lattice bound show that an accepted input is a prime power; elementary preprocessing excludes nontrivial perfect powers. We construct $b$ deterministically using Jacobi sums and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner, which extends OpenAI's Hecke zero-free theorem. The total bit complexity is $L^{32+o(1)}$, where $L=\lceil\log_2 n\rceil$, and verification after constructing $b$ costs $L^{6+o(1)}$. More generally, for a fixed real algebraic $1/2\leθ<1$, a common zero-free boundary $\Re s>θ$ for the relevant Dedekind zeta functions gives $L^{\max\{6,(1-θ)^{-1}\}+o(1)}$. This bound reaches $L^{6+o(1)}$ at $θ=5/6$, and hence under GRH. We state a fixed-base modification of Agrawal's conjecture for odd integers passing the base-$2$ Fermat test, using the modulus $X^r-2$ with $r$ the least positive integer not dividing $n(n-1)$.

0.44

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

cs.CC ·2026-08-14 ·Isaac M Hair, Amit Sahai
theory similarity 0.63
Abstract

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

0.32

$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals

cs.CC ·2026-11-10 ·Yansong Feng, Jiaqi Liu, Hengyi Luo, Yanbin Pan
theory similarity 0.63
Abstract

We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduction from the Subset Sum problem. For an instance with $s$ positive input integers, the output lattice has dimension $O(s)$. A solution to the original Subset Sum instance can be recovered in polynomial time from any nonzero output lattice vector of norm at most the specified bound. We also transfer these reductions from $R_n$ to the power-of-two cyclic rings $S_{2n}=\mathbb{Z}[X]/(X^{2n}-1)$. This gives $\mathsf{NP}$-completeness of decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm for principal ideals and free modules of any fixed positive rank over these rings.

0.19

CVP Is NP-Complete for Principal Cyclotomic Ideals

cs.CC ·2026-08-24 ·Jiaqi Liu, Yansong Feng, Yanbin Pan
theory similarity 0.63
Abstract

We prove that exact Euclidean decision-CVP is $\mathsf{NP}$-complete on the coefficient lattices of nonzero principal ideals in the power-of-two cyclotomic rings $R_d:=\mathbb{Z}[y]/(y^d+1)$. Our deterministic reduction from Exact Cover by 3-Sets (X3C) produces a target and a squared threshold $Δ$ such that the closest squared distance is exactly $Δ$ in YES instances and at least $Δ+4$ in NO instances. This also implies $\mathsf{NP}$-hardness of exact search-CVP under polynomial-time Turing reductions. We also transfer the resulting principal-ideal CVP instances to full-rank principal ideals of the cyclic quotient ring $\mathbb{Z}[X]/(X^D-1)$, where $D:=2d$. Their coefficient lattices are invariant under cyclic coordinate shifts. The lift preserves principality and multiplies corresponding squared distances by eight. Thus, on principal cyclic ideal lattices, exact decision-CVP is $\mathsf{NP}$-complete and exact search-CVP is $\mathsf{NP}$-hard. We also obtain uniformly computable fixed cyclotomic and cyclic families in which only the target and threshold depend on the X3C collection. Consequently, a polynomial-time solution to exact decision-CVPP on either family would imply $\mathsf{NP}\subseteq\mathsf{P}/\mathrm{poly}$ and collapse the polynomial hierarchy to $Σ_2^{\mathsf{P}}$. To our knowledge, the cyclic results answer Micciancio's questions of whether exact decision-CVP is $\mathsf{NP}$-hard on cyclic lattices and on a fixed family of cyclic lattices, even when restricted to full-rank principal cyclic ideals. Finally, under the coefficient embedding, we prove that exact decision-module-SIVP is $\mathsf{NP}$-complete on free rank-two modules over the same cyclotomic rings.

0.38

A Degree--Size Relation for Resolution over Polynomials

cs.CC cs.LO ·2026-09-30 ·Shuo Pang
similarity 0.61
Abstract · Parameters in Section 8 (Conclusions) made explicit

For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime field. Applications include exponential lower bounds for CNFs in $\operatorname{Res}(\operatorname{PC}_r/\mathbb{F}_p)$ and hence in $\operatorname{Res}(\oplus_p)$, separations between different moduli, improved lower bounds for $\operatorname{Res}(k)$ up to $k=\varepsilon\log n$, proof-search consequences, and an implication of super-polynomial $AC^0[p]$-Frege bounds from very strong PC degree lower bounds. The proof uses the common-multiplier idea isolated from Braun [arXiv:2609.23015] to construct a Razborov--Smolensky approximation that preserves inferences, without introducing extension variables. The approximation errors are measured by ranks of the multiplication maps induced by the error-witness polynomials, modulo bounded-degree PC consequences.

0.49

Deterministic Shift Equivalence Testing for Sparse Polynomials

cs.DS cs.CC ·2026-10-19 ·Markus Bläser, Pranjal Dutta, Sagnik Dutta, Gorav Jindal
top venue similarity 0.61
Abstract · To appear in SODA 2027

We study the shift equivalence testing problem for high-degree sparse multivariate polynomials. Given explicit spar se representations of two polynomials $f,g\in\mathbb{Q}[x_1,\ldots,x_n]$, with exponents encoded in binary, sparsities $s$ and $t$, and total degree at most $d$, the task is to decide whether there is a vector $\mathbf{a}\in\mathbb{Q}^n$ such that $f(\mathbf{x}+\mathbf{a})\equiv g(\mathbf{x})$. Furthermore, one needs to output such a vector if it exists. Dvir, Oliveira, and Shpilka (ICALP 2014) studied shift equivalence for low-degree arithmetic circuits. Their framew ork does not apply directly to sparse polynomials, which are not closed under shifts, and they left open whether shift equivalence of sparse polynomials admits an efficient deterministic algorithm. We answer this question positively over $\mathbb{Q}$. If the input coefficients have bit-size at most $τ$, we sh ow that a rational shift of polynomial bit-size exists whenever the polynomials are shift equivalent. Moreover, our alg orithm outputs such a shift and has a running time of $\operatorname{poly}(n,s,t,τ,\log d)$ in the bit model. The ar ithmetic and structural parts of our result also hold over any field of characteristic zero or characteristic larger th an $d$.

0.37