Monomial Testing and Applications

2013/03/03 by Shenshi Chen, Chen, Shenshi · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CC

paper · pdf · doi:10.48550/arxiv.1303.0478

17 pages, 4 figures, submitted FAW-AAIM 2013. arXiv admin note: substantial text overlap with arXiv:1302.5898; and text overlap with arXiv:1007.2675, arXiv:1007.2678, arXiv:1007.2673 by other authors

openalex publication_date 2013/03/03 · arxiv created 2013/04/12 · arxiv updated 2013/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we devise two algorithms for the problem of testing q-monomials of degree k in any multivariate polynomial represented by a circuit, regardless of the primality of q. One is an O^*(2^k) time randomized algorithm. The other is an O^*(12.8^k) time deterministic algorithm for the same q-monomial testing problem but requiring the polynomials to be represented by tree-like circuits. Several applications of q-monomial testing are also given, including a deterministic O^*(12.8^mk) upper bound for the m-set k-packing problem.

Citations

• Towards Randomized Testing of q-Monomials in Multivariate Polynomials
• Algorithms for Testing Monomials in Multivariate Polynomials
• The Complexity of Testing Monomials in Multivariate Polynomials

Cited by

• Faster Deterministic Algorithms for Packing, Matching and t-Dominating Set Problems

Related

• Towards Randomized Testing of q-Monomials in Multivariate Polynomials
• Algorithms for Testing Monomials in Multivariate Polynomials
• Randomized Polynomial Time Identity Testing for Noncommutative Circuits
• A Simple Algorithm for Hamiltonicity
• The Complexity of Testing Monomials in Multivariate Polynomials