Toward randomized testing of q-monomials in multivariate polynomials

DOI10.1142/S1793830914500165zbMATH Open1372.68291arXiv1302.5898MaRDI QIDQ2875680FDOQ2875680

Authors: Shenshi Chen, Yaqing Chen, Quanhai Yang 

Publication date: 11 August 2014

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

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$.

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

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

zbMATH Keywords

complexityrandomized algorithmsalgebramonomialsmultivariate polynomialsmonomial testing

Mathematics Subject Classification ID

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

Cites Work

• Narrow sieves for parameterized paths and packings
• Faster Algebraic Algorithms for Path and Packing Problems
• Learning DNF in time
• The complexity of testing monomials in multivariate polynomials
• Algorithms for 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)