{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T17:18:00Z","timestamp":1648574280060},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p> Given any fixed integer q \u2265 2, a q-monomial is of the format [Formula: see text] such that 1 \u2264 s<jats:sub>j<\/jats:sub> \u2264 q - 1, 1 \u2264 j \u2264 t. q-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and q-monomials for prime q in multivariate polynomials relies on the property that Z<jats:sub>q<\/jats:sub> is a field when q \u2265 2 is prime. When q &gt; 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.15<jats:sup>k<\/jats:sup>) 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 &gt; 7. <\/jats:p>","DOI":"10.1142\/s1793830914500165","type":"journal-article","created":{"date-parts":[[2014,1,17]],"date-time":"2014-01-17T03:38:38Z","timestamp":1389929918000},"page":"1450016","source":"Crossref","is-referenced-by-count":0,"title":["TOWARD RANDOMIZED TESTING OF q-MONOMIALS IN MULTIVARIATE POLYNOMIALS"],"prefix":"10.1142","volume":"06","author":[{"given":"SHENSHI","family":"CHEN","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas-Pan American, Edinburg, TX 78539, USA"}]},{"given":"YAQING","family":"CHEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas-Pan American, Edinburg, TX 78539, USA"}]},{"given":"QUANHAI","family":"YANG","sequence":"additional","affiliation":[{"name":"College of Information Engineering, Northwest A&amp;F University, Yangling, Shaanxi 712100, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2014,3,19]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012-9496-5"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.038"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"rf15","first-page":"329","volume":"8","author":"Fu B.","journal-title":"Acta Math. Sinica"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"rf19","volume-title":"Perceptrons","author":"Minksy M.","year":"1968"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830914500165","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:44:15Z","timestamp":1565192655000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830914500165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,19]]},"references-count":13,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2014,3,19]]},"published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1142\/S1793830914500165"],"URL":"https:\/\/doi.org\/10.1142\/s1793830914500165","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3,19]]}}}