5 papers · 1 filter
Complexity of Low-Degree Skew Polynomial Multiplication over Finite Fields
Ke Ye, Yichuan Cao, Ruichen Qiu
In this note, we study the complexity of multiplication in skew polynomial rings over finite fields. We prove that the product of two elements in of degree…
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…
A Finite Certificate for the Positive Vasc Inequality
Dakai Guo, Ruichen Qiu, Yichuan Cao +1
We prove the positive-real case of the Vasc cyclic inequality. The proof was obtained with human-guided assistance from the AI agent MechMath Agent Team: the human-readable p…