2 citations · 8 across the 15 of their papers we have counts for
15 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…
Sparse Polynomial GCD Cannot Be Computed in Fixed-output Polynomial Time
Ruichen Qiu, Yichuan Cao, Qiao-Long Huang +2
This paper shows that, assuming , sparse univariate polynomial GCD cannot be computed in fixed-output polynomial time over any fixed computable field. Pre…
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…
Bit Complexity of Polynomial GCD on Sparse Representation
Qiao-Long Huang, Xiao-Shan Gao
An input- and output-sensitive GCD algorithm for multi-variate polynomials over finite fields is proposed by combining the modular method with the Ben-Or/Tiwari sparse interpolatio…
Skew-sparse matrix multiplication
Qiao-Long Huang, Ke Ye, Xiao-Shan Gao
Based on the observation that is isomorphic to a quotient skew polynomial ring, we propose a new method for matrix multiplicat…
Sparse Polynomial Interpolation Based on Derivative
Qiao-Long Huang
In this paper, we propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program(SLP). Both of our algorithms work over any fin…
Sparse Polynomial Interpolation Based on Diversification
Qiao-Long Huang
We consider the problem of interpolating a sparse multivariate polynomial over a finite field, represented with a black box. Building on the algorithm of Ben-Or and Tiwari for inte…
Revisit Sparse Polynomial Interpolation based on Randomized Kronecker Substitution
Qiao-Long Huang, Xiao-Shan Gao
In this paper, a new reduction based interpolation algorithm for black-box multivariate polynomials over finite fields is given. The method is based on two main ingredients. A new…
Deterministic Interpolation of Sparse Black-box Multivariate Polynomials using Kronecker Type Substitutions
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we propose two new deterministic interpolation algorithms for a sparse multivariate polynomial given as a standard black-box by introducing new Kronecker type substi…
Faster Interpolation Algorithms for Sparse Multivariate Polynomials Given by Straight-Line Programs\
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let be an -va…
Sparse Rational Function Interpolation with Finitely Many Values for the Coefficients
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we give new sparse interpolation algorithms for black box univariate and multivariate rational functions h=f/g whose coefficients are integers with an upper bound. T…
Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we give new sparse interpolation algorithms for black box polynomial f whose coefficients are from a finite set. In the univariate case, we recover f from one evalua…