ECCC-Report TR13-139https://eccc.weizmann.ac.il/report/2013/139Comments and Revisions published for TR13-139en-usTue, 08 Oct 2013 08:45:10 +0300
Paper TR13-139
| Detecting Monomials with $k$ Distinct Variables |
Peter Floderus,
Andrzej Lingas,
Mia Persson,
Dzmitry Sledneu
https://eccc.weizmann.ac.il/report/2013/139We 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.$ Tue, 08 Oct 2013 08:45:10 +0300https://eccc.weizmann.ac.il/report/2013/139