We study the complexity of detecting monomialswith special properties in the sum-productexpansion of a polynomial represented by an arithmeticcircuit of size polynomial in the number of inputvariables and using only multiplication and addition.We focus on monomial properties expressed in termsof the number of distinct variables occurringin a monomial. Our main result is a randomized FPT algorithm fordetection of a monomial having at least k distinct variables, parametrized by the degreeof the polynomial. Furthermore,we derive several hardnessresults on detection of monomials with such propertieswithin exact, parametrized and approximation complexity.In particular, we observe that the detectionof a monomialhaving at most k distinct variables is W[2]-hardfor the parameter k
展开▼
