2013/02/24 by Shenshi Chen, Chen, Shenshi, Yaqing Chen +3 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1302.5898
21 pages, 5 figures. arXiv admin note: text overlap with arXiv:1007.2675, arXiv:1007.2678, arXiv:1007.2673 by other authors
arxiv created 2013/08/12 · arxiv updated 2013/08/14
Given any fixed integer q≥ 2, a q-monomial is of the format xs1i1xs2i2...xitst such that 1≤ sj ≤ q-1, 1≤ j ≤ t. q-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and q-monomails for prime q in multivariate polynomials relies on the property that Zq is a field when q≥ 2 is prime. When q>2 is not prime, it remains open whether the problem of testing q-monomials can be solved in some compatible complexity. In this paper, we present a randomized O^*(7.15k) algorithm for testing q-monomials of degree k that are found in a multivariate polynomial that is represented by a tree-like circuit with a polynomial size, thus giving a positive, affirming answer to the above question. Our algorithm works regardless of the primality of q and improves upon the time complexity of the previously known algorithm for testing q-monomials for prime q>7.