Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-139 | 7th October 2013 15:40

Detecting Monomials with $k$ Distinct Variables



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

ISSN 1433-8092 | Imprint