CS Paper Radar

Refined complexity bounds for rational reconstruction and XGCD through Padé approximants and Cauchy interpolants

Vincent Neiger, Mohab Safey El Din, Kevin Tran

cs.SC ·submitted 2026-09-17 20:12 UTC · v1

Abstract

When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the half-gcd algorithm. These problems have various applications in algebraic computations and bear strong connections to linearly recurrent sequences, structured matrices, and continued fractions. This article first gives a collection of algorithmic reductions, showing that rational reconstruction and XGCD can be solved via the computation of bases of relations modulo a freely-chosen polynomial $M(x)$. In particular, one recovers the folklore idea that bases of Padé approximants (i.e., $M(x) = x^d$) can be used to perform quasi-linear rational reconstruction or XGCD, extending to fast algorithms the well-known link between the Berlekamp-Massey algorithm and the extended Euclidean algorithm. One highlight of these reductions is that, instead of approximants, one may rely on Cauchy interpolants (i.e., $M(x)$ vanishes at chosen points). In a second part, this article describes divide-and-conquer algorithms for approximants and interpolants along with complexity analyses showing an explicit leading constant in front of the dominant term. For interpolants, the best leading constant is obtained through a variant that stores polynomials represented by evaluations, and exploits fast extrapolation in order to avoid repeated conversions to the monomial basis; this requires special points, in geometric or arithmetic progression, or FFT points when the base field allows them. Combining the analyses with the reductions leads to the best complexity bounds we are aware of for rational reconstruction and XGCD. Perhaps surprisingly, even Padé approximants or Berlekamp-Massey-like computations, which intrinsically involve $M(x) = x^d$, are accelerated by reducing them to Cauchy interpolation at well-chosen points.

Closest papers

Nearest neighbours by meaning across the whole index.

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.58
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

CVP Is NP-Complete for Principal Cyclotomic Ideals

cs.CC ·2026-08-24 ·Jiaqi Liu, Yansong Feng, Yanbin Pan
theory similarity 0.58
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

Integer Programming with Polyhedral Constraints on the Image

cs.DS ·2026-11-12 ·Anubhav Dhar, Tim Randolph, Karol Węgrzycki
similarity 0.58
Abstract

We generalize integer programming to the setting in which the image $A \mathbf{x}$ is restricted to an explicitly given rational polyhedron $P$. That is, we solve $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}\in P, \mathbf{x}\in\mathbb{Z}_{\geq 0}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and $P$ is an explicitly given rational polyhedron. We present a randomized algorithm running in time $(dΔ)^{O(d)}\operatorname{poly}(L)$ in this regime, where $Δ:= \|A\|_\infty$ and $L$ is the binary input length. This running time matches that of the best-known parameterized algorithms for integer programming, due to Eisenbrand and Weismantel and to Jansen and Rohwedder, and improves on the $O(d^2)$ exponent achieved by Dadush, Léonard, Rohwedder, and Verschae in a more general setting. This result enables several applications, including exact algorithms for integer programming and unbounded knapsack in which the consumed resources $A\mathbf{x}$ must satisfy arbitrary additional linear constraints. We also obtain a randomized fixed-parameter algorithm for Unbounded Subset Sum parameterized by the doubling constant, resolving an open problem of Randolph and Węgrzycki. For integer programs with $m$ constraints and bounded row doubling, we obtain an $f(C,m)n^{O(m)}\operatorname{poly}(L)$-time algorithm and show that the dependence on $m$ in the exponent of $n$ is necessary under $\mathsf{W[1]}\ne\mathsf{FPT}$.

0.24

Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space

cs.DS cs.CR ·2026-11-05 ·Jiseung Kim, Minkyu Kim, Hyung Tae Lee
similarity 0.57
Abstract · 30 pages, 1 figure

We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant. It uses $\poly(p,\ell)$ working space outside the oracle, and all oracle queries have rank $N$ and $\poly(p,\ell)$ bit complexity. For $p=2$, the reduction transfers polynomial-space exact SVP algorithms to exact CVP with $2^{O(N)}\poly(\ell)$ time overhead. Instantiating it with the SVP algorithms of Kannan and of Feng, Gao and Liu yields randomized polynomial-space CVP algorithms running in time $N^{N/(2e)+o(N)}$ and $N^{N/(4e)+o(N)}$, respectively. For every fixed integer $p\ge3$, the same reduction yields exact $\ell_p$-CVP algorithms for arbitrary rational targets either in randomized time and space $2^{O(N)}$, or in randomized time $N^{N/(4e)+o(N)}$ and polynomial space. These algorithmic bounds are up to polynomial factors in $\ell$. The reduction performs local search sequentially over the cosets of \(2L\), where \(L\) is the input lattice, while tracking the excess of the current objective value over the optimum. Within a coset containing a closest vector, midpoint inequalities bound the unknown correction in terms of this excess, which in turn allows us to construct many short corrections that reduce the excess bound by a factor of four. A counting argument shows that these improving corrections form a sufficiently large fraction of the lattice points in a known search region, and a sparsification-based sampler assigns sufficiently large probability to every nonzero vector in that region, using at most one SVP call per sample. For \(p\ge3\), the same framework is extended using a diagonal weighted norm computed from the current point.

0.30

A Degree--Size Relation for Resolution over Polynomials

cs.CC cs.LO ·2026-09-30 ·Shuo Pang
similarity 0.57
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

$\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.56
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

Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters

cs.DS math.AC ·2026-09-08 ·Qiao-Long Huang, Xiao-Shan Gao
similarity 0.56
Abstract

Let $A, B \in \mathbb{Z}[x_1, \dots, x_n]$ be multivariate polynomials with integer coefficients and let $G = \gcd(A, B)$. We present an algorithm for computing $G$ whose expected bit complexity is asymptotically linear in all fundamental parameters: the number of variables $n$, the term count $T = \max\{\|A\|_0, \|B\|_0, \|G\|_0\}$, the total degree $D$, and the logarithmic coefficient sizes $\log\Hi$ and $\log\Ho$, where $\Hi$ bounds the coefficients of the inputs and $\Ho$ bounds those of the GCD. The bit complexity is characterized by the clean bound \[ \widetilde{O}\bigl( n \cdot T \cdot D \cdot \log\Hi \cdot \log\Ho \bigr). \] To our knowledge, this is the first sparse GCD algorithm over the integers that achieves linear complexity in all these parameters simultaneously. The integer algorithm is built upon a new field GCD algorithm. For $A, B \in \K[x_1, \dots, x_n]$ over a field $\K$ with $\operatorname{char}(\K) = 0$ or $\operatorname{char}(\K) > °G$, we give the first algorithm that computes $G = \gcd(A,B)$ with expected \[ \widetilde{O}\bigl( n \cdot T \cdot D \bigr) \] field operations, which is both input- and output-sensitive. The key technical contribution behind both algorithms is a derivative-aided separated Hensel lifting technique introduced in this paper. By introducing an auxiliary variable and leveraging derivative information, our scheme extracts all partial exponents via a single $z^2$-lift per variable, achieving constant sequential depth $O(1)$. This stands in sharp contrast to classical Hensel lifting, which requires $O(D)$ sequential lifting steps and suffers from representation densification in the sparse setting. The field algorithm is then extended to the integer case through modular reduction and rational reconstruction.

0.31

Long rational and Gaussian integer multiplication

cs.DS math.NT ·2026-11-13 ·Yuval Spiizer, Raphael S. Steiner
similarity 0.56
Abstract · 38 pages

Long integer multiplication is a fundamental operation in computational algebra, heavily relying on Toom--Cook and related evaluation-interpolation algorithms. Conventional wisdom dictates that multiplication on the Gaussian integers $\mathbb{Z}[i]$ is reduced to standard rational integer multiplication, since $\mathbb{Z}[i]$ is a ring extension of $\mathbb{Z}$. We show that this approach is far from optimal and moreover inverting this established paradigm, that is reducing rational to Gaussian multiplication, leads to faster rational integer multiplication algorithms. We introduce a novel Toom--Cook framework that reduces rational long integer multiplication to Gaussian integer multiplication, yielding a strictly more efficient computational pipeline. By taking advantage of the special properties of the rational integer domain inside the Gaussian integers, we achieve a more favourable algebraic structure that reduces the overall arithmetic cost in every metric. To validate this theoretical shift, we provide a complete implementation of our algorithm. Benchmarks demonstrate that our approach outperforms the highly optimised GNU Multiple Precision Arithmetic Library (GMP) by up to 29\%, bridging a fundamental theoretical insight with significant practical improvements in high-performance computer algebra.

0.20