Toward randomized testing of q-monomials in multivariate polynomials

DOI10.1142/S1793830914500165MaRDI QIDQ2875680zbMATH OpenFDO

Authors Shenshi Chen, Yaqing Chen, Quanhai Yang

Publication date 11 August 2014

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.5898

zbMATH Keywords

complexityrandomized algorithmsalgebramonomialsmultivariate polynomialsmonomial testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Abstract: Given any fixed integer $qge2$, a $q$-monomial is of the format $displaystyle{x}_{i_1}^{s_1}{x}_{i_2}^{s_2}\mathrm{...}{x}_{i_t}^{s_t}$ such that $1le{s}_{j}leq-1$, $1lejlet$. $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 $Z_q$ is a field when $qge2$ 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^{\ast }(7.15^k)$ 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$.

Recommendations

• Monomial testing and applications
• Algorithms for testing monomials in multivariate polynomials
• On testing monomials in multivariate polynomials
• The complexity of testing monomials in multivariate polynomials
• Detecting monomials with \(k\) distinct variables

Cites work

• Algorithms for testing monomials in multivariate polynomials
• Faster Algebraic Algorithms for Path and Packing Problems
• Learning DNF in time
• Narrow sieves for parameterized paths and packings
• The complexity of testing monomials in multivariate polynomials

Cited in

(6)

• On testing monomials in multivariate polynomials
• Algorithms for testing monomials in multivariate polynomials
• The complexity of testing monomials in multivariate polynomials
• Distribution-free testing for monomials with a sublinear number of queries
• Optimal testing of multivariate polynomials over small prime fields
• Monomial testing and applications

This page was built for publication: Toward randomized testing of \(q\)-monomials in multivariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875680)