Algorithms for testing monomials in multivariate polynomials

DOI10.1007/978-3-642-22616-8_2MaRDI QIDQ5199136zbMATH OpenOpenAlexFDO

Authors Zhi-Xiang Chen, Bin Fu, Yang Liu, Robert T. Schweller

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

zbMATH Keywords

randomizationcomplexityalgebraderandomizationmultivariate polynomialsmonomial testing

Mathematics Subject Classification ID

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

Abstract: This paper is our second step towards developing a theory of testing monomials in multivariate polynomials. The central question is to ask whether a polynomial represented by an arithmetic circuit has some types of monomials in its sum-product expansion. The complexity aspects of this problem and its variants have been investigated in our first paper by Chen and Fu (2010), laying a foundation for further study. In this paper, we present two pairs of algorithms. First, we prove that there is a randomized $O^{\ast }(p^k)$ time algorithm for testing $p$-monomials in an $n$-variate polynomial of degree $k$ represented by an arithmetic circuit, while a deterministic $O^{\ast }(6.4^k+p^k)$ time algorithm is devised when the circuit is a formula, here $p$ is a given prime number. Second, we present a deterministic $O^{\ast }(2^k)$ time algorithm for testing multilinear monomials in $P{i}_{m}Sigm{a}_{2}P{i}_{t}imesP{i}_{k}P{i}_3$ polynomials, while a randomized $O^{\ast }(1.5^k)$ algorithm is given for these polynomials. The first algorithm extends the recent work by Koutis (2008) and Williams (2009) on testing multilinear monomials. Group algebra is exploited in the algorithm designs, in corporation with the randomized polynomial identity testing over a finite field by Agrawal and Biswas (2003), the deterministic noncommunicative polynomial identity testing by Raz and Shpilka (2005) and the perfect hashing functions by Chen {em at el.} (2007). Finally, we prove that testing some special types of multilinear monomial is W[1]-hard, giving evidence that testing for specific monomials is not fixed-parameter tractable.

Recommendations

• On testing monomials in multivariate polynomials
• The complexity of testing monomials in multivariate polynomials
• Monomial testing and applications
• Toward randomized testing of \(q\)-monomials in multivariate polynomials
• Detecting monomials with \(k\) distinct variables

Cited in

(13)

• On testing monomials in multivariate polynomials
• Fast exact algorithms using Hadamard product of polynomials
• Enumeration of the monomials of a polynomial and related complexity classes
• Algorithmic local monomialization of a binomial: A comparison of different approaches
• The complexity of testing monomials in multivariate polynomials
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• 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
• Detecting monomials with \(k\) distinct variables
• Fast Exact Algorithms Using Hadamard Product of Polynomials
• Toward randomized testing of \(q\)-monomials in multivariate polynomials
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Monomial testing and applications

This page was built for publication: Algorithms for testing monomials in multivariate polynomials

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