{"id":"arxiv/2609.08074","url":"https://arxiv.org/abs/2609.08074","tags":["math.AC","cs.DS"],"score":0,"title":"Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters","domain":"math.AC","source":"arxiv","authors":["Qiao-Long Huang","Xiao-Shan Gao"],"reviews":0,"subject":"math.AC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}