2 citations · 8 across the 15 of their papers we have counts for
11 papers · 1 filter
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…
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…