The complexity of testing monomials in multivariate polynomials

DOI10.1007/978-3-642-22616-8_1MaRDI QIDQ5199135zbMATH OpenOpenAlexFDO

Authors Zhi-Xiang Chen, Bin Fu

Publication date 12 August 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

complexityalgebramultivariate polynomialsmonomial testingmultilinear monomials

Mathematics Subject Classification ID

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

Abstract: The work in this paper is to initiate a theory of testing monomials in multivariate polynomials. The central question is to ask whether a polynomial represented by certain economically compact structure has a multilinear monomial in its sum-product expansion. The complexity aspects of this problem and its variants are investigated with two folds of objectives. One is to understand how this problem relates to critical problems in complexity, and if so to what extent. The other is to exploit possibilities of applying algebraic properties of polynomials to the study of those problems. A series of results about $PiSigmaPi$ and $PiSigma$ polynomials are obtained in this paper, laying a basis for further study along this line.

Recommendations

• On testing monomials in multivariate polynomials
• Algorithms for testing monomials in multivariate polynomials
• Monomial testing and applications
• Toward randomized testing of q-monomials in multivariate polynomials

Cited in

(12)

• On testing monomials in multivariate polynomials
• scientific article; zbMATH DE number 2125608 (Why is no real title available?)
• Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks
• Algorithms for testing monomials in multivariate polynomials
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• A polynomial-time dependence test for determining integer-valued solutions in multi-dimensional arrays under variable bounds
• Binomiality testing and computing sparse polynomials via witness sets
• Detecting monomials with k distinct variables
• Optimal testing of multivariate polynomials over small prime fields
• Toward randomized testing of q-monomials in multivariate polynomials
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• Monomial testing and applications

This page was built for publication: The complexity of testing monomials in multivariate polynomials

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