1 citations · 3 across the 10 of their papers we have counts for
10 papers
A New Sparse Algorithm for Polynomial GCD over Integers
Qiao-Long Huang, Michael Monagan
We describe a new greatest common divisor (GCD) algorithm for polynomials with integer coefficients. The bit complexity of the new algorithm is polynomial in the input and output s…
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Qiao-Long Huang, Xiao-Shan Gao
Let be multivariate polynomials with integer coefficients and let . We present an algorithm for computing whose expected…
Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree
Qiao-Long Huang, Yichuan Cao, Ruichen Qiu +1
We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let $f \in \F[x_1,\ldots,x_n]$ be a nonzero polynomial that i…
Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard
Ruichen Qiu, Yichuan Cao, Qiao-Long Huang +2
In this paper, we prove that output-sensitive sparse polynomial GCD computation over finite fields is NP-hard under BPP many-one reduction. More precisely, for two sparse univariat…
Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard
Yichuan Cao, Ruichen Qiu, Qiao-Long Huang +2
In this paper, we show that deciding whether a sparse polynomial does not divide another sparse polynomial exactly over finite fields is NP-hard under BPP many-one reductions. Equi…
Quasi-linear Time Multiplication of Sparse Polynomials with Integer Coefficients
Qiao-Long Huang, Yichuan Cao, Ruichen Qiu +1
Sparse polynomial multiplication is a fundamental problem in computer algebra and the theory of computation, and the development of a quasi-linear time output-sensitive multiplicat…