TR13-139 Authors: Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Publication: 8th October 2013 08:45

Downloads: 994

Keywords:

We study the complexity of detecting monomials

with special properties in the sum-product

expansion of a polynomial represented by an arithmetic

circuit of size polynomial in the number of input

variables and using only multiplication and addition.

We focus on monomial properties expressed in terms

of the number of distinct variables occurring

in a monomial. Our main result is

a randomized FPT algorithm for

detection of a monomial having at least $k$

distinct variables, parametrized by the degree

of the polynomial. Furthermore,

we derive several hardness

results on detection of monomials with such properties

within exact, parametrized and approximation complexity.

In particular, we observe that the detection

of a monomial

having at most $k$ distinct variables is $W[2]$-hard

for the parameter $k.$