CS Paper Radar

Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters

Qiao-Long Huang, Xiao-Shan Gao

cs.DS math.AC ·submitted 2026-09-08 00:35 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Finding Integer Roots of Polynomials in Nearly Optimal Time

cs.DS math.NTcs.SC ·2026-11-03 ·Yansong Feng, Itamar Nir
theory similarity 0.64
Abstract

Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\widetilde O(nb+\min(n,b)^3b^2)$, which is $\widetilde O(nb)$ whenever $b\leq n^{1/4}$. This answers a question of Harvey and Hittmeir (2022), who asked whether integer roots can be found deterministically in quasilinear time, conditionally on Pan's theorem, and unconditionally for $b\leq n^{1/4}$. The fastest previous deterministic algorithm, due to Nir, takes $\widetilde O(n^{3/2}b)$ bit operations and works only for square-free polynomials. Instead of $p$-adic lifting, we combine approximate complex root finding with exact polynomial evaluation. We first approximate the complex roots of the polynomial formed by the top $\min(n,b)+1$ coefficients of $f$. Every integer root $r$ of $f$ with $|r|\geq 2$ lies within distance $2$ of some complex root of this truncated polynomial. Rounding the real parts of the approximate roots therefore gives a list of $O(\min(n,b))$ candidate integers that is guaranteed to contain all integer roots of $f$. Although a single candidate can have up to $b$ bits, a bound via the Mahler measure shows that the bit lengths of all candidates sum to $O(b)$. This allows us to test all candidates by exact multipoint evaluation in $\widetilde O(nb)$ bit operations.

0.21

Computing the Determinant via the Generalized Euclidean Algorithm

cs.DS cs.SC ·2026-08-22 ·Janina Reuter
similarity 0.63
Abstract

We present an algorithm with a natural geometric interpretation for computing the determinant of a matrix $B\in\mathbb{Z}^{d\times d}$. It improves upon the current fastest deterministic algorithms by a factor of $d^{ω(1)+1-ω(2)}\approx d^{0.1213}$, where $ω(k)$ denotes the exponent required for multiplying a $d\times d$ matrix with a $d\times d^k$ matrix. Our approach builds on a recent result of Klein and Reuter (STOC 2025), who introduced a novel algorithmic idea for lattice basis computation that can be viewed as extending the Euclidean algorithm from $\mathbb{Z}$ to $\mathbb{Z}^d$. By adapting their techniques, we compute the determinant with the same bit complexity as applying the generalized Euclidean algorithm to an input matrix $A\in\mathbb{Z}^{d\times 2d}$ with $\|A\| = \|B\|$, namely $\tilde{O}(d^{ω(2)}\log\|B\|)$. Prior to this work, the fastest deterministic algorithm for computing the determinant required $\tilde{O}(d^{ω(1)+1}\log\|B\|)$ bit operations.

0.22

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations

cs.DS cs.CCmath.NA ·2026-09-29 ·Jonathan A. Kelner
similarity 0.63
Abstract

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $ε$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $κ$.

0.09

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

Bounded Integer Programming in Almost $N^{2d}$ Time

cs.DS ·2026-10-19 ·Lin Chen, Yuchen Mao, Guochuan Zhang
theory similarity 0.62
Abstract

We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\ \mathbf{x}\in\mathbb{Z}^n\}$, where $A\in\mathbb{Z}^{d\times n}$, all entries of $\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u}$ are integers, and every variable bound is finite. Let $N$ be an upper bound on the absolute values of the entries of $A$, and $c_{\max}$ one on the absolute values of the costs. For every fixed $d$ and every fixed $\varepsilon>0$ we give a deterministic algorithm running in time \[ T_{\textrm LP}+O_d(n)+O_{d,\varepsilon}\bigl(N^{2d+\varepsilon}\log^2(c_{\max}+2)\bigr), \] where $T_{\textrm LP}$ is the time to solve one linear programming relaxation exactly. Prior to our work, the best known running time for bounded variables was $N^{O(d^2)}$ [Eisenbrand \& Weismantel'20], and it has been a fundamental open problem whether the exponent $O(d^2)$ can be improved to one linear in $d$. We answer this question affirmatively, with the exponent $2d+\varepsilon$.

0.16

Bounds on polynomial approximations of the discrete logarithm function

cs.CC cs.CR ·2026-10-24 ·Swastik Kopparty, Rishabh Kothary, Ashutosh Shankar
publishedtheory similarity 0.62
Abstract

We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, dlog(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.

0.41

Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes

cs.IT ·2026-10-31 ·Li Zhu, Hongfeng Wu
theory similarity 0.62
Abstract

For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

0.20

Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization

cs.DS ·2026-11-12 ·Klaus Jansen, Felix Ohnesorge, Björn Schumacher
similarity 0.61
Abstract

We consider a special block-structured integer program with $n$ blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective $c^{\intercal}x + g(Ax)$, where $c$ is a rational cost vector, $A$ is an integral matrix with $d$ rows, and $g \colon \mathbb{Z}^d \to \mathbb{Q}\cup \{+\infty\}$ is an arbitrary function. We access $g$ via an oracle that minimizes $c^{\intercal}x + g(Ax)$ when all but $O(d)$ variables are fixed. Our algorithm runs in time $(ndΔ)^{O(d)}(Q + \text{poly}(|I|))$ where $Δ$ is the largest absolute value of an entry in $A$, $Q$ is the necessary time to evaluate the oracle for $g$ and $|I|$ is the size of the input. This model is a variation of the model studied by Dadush et al.~[IPCO 23]. Their model has only a single block but individual upper and lower bounds on the variables instead of prescribed block sums. For their model they present an algorithm with running time $t^d(dΔ)^{O(d^2)}Q$ where $t$ is the number of variables. We use our algorithm to solve mixed-integer linear programs with no upper bounds on the variables, a linear objective, and arbitrarily many constraints involving only fractional variables in time $(mΔ)^{O(m)}\text{poly}(|I|)$, where $m$ is the number of constraints involving integral variables and $Δ$ is the largest absolute value of coefficients of integral variables. This improves the dependence on $m$ in the exponent to asymptotically match the dependency in the integer setting. Further, we use our algorithm to generalize the parameterized algorithm for scheduling on uniformly related machines by Rohwedder~[ICALP 25] to obtain an algorithm for multiple knapsack with running time $w_{\max}^{O(d)}\text{poly}(|I|)$ where $w_{\max}$ is the maximum weight of an item and $d$ the number of different weights.

0.26