4 papers
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…