Detecting monomials with k distinct variables
(2015) In Information Processing Letters 115(2). p.8286 Abstract
 We study the complexity of detecting monomials with special properties in the sumproduct 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 first result is a randomized FPT algorithm for detection of a monomial having at least k distinct variables, parametrized with respect to k. For a more restricted class of circuits, we can also provide a deterministic FPT algorithm for detection of a monomial having at most k distinct variables parametrized by the degree of the polynomial represented by the input circuit.... (More)
 We study the complexity of detecting monomials with special properties in the sumproduct 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 first result is a randomized FPT algorithm for detection of a monomial having at least k distinct variables, parametrized with respect to k. For a more restricted class of circuits, we can also provide a deterministic FPT algorithm for detection of a monomial having at most k distinct variables parametrized by the degree of the polynomial represented by the input circuit. 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. (C) 2014 Elsevier B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/4941538
 author
 Floderus, Peter ^{LU} ; Lingas, Andrzej ^{LU} ; Persson, Mia ^{LU} and Sledneu, Dzmitry ^{LU}
 organization
 publishing date
 2015
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Algorithms, Polynomial, Monomial, Arithmetic circuit, Parametrized, complexity, Approximation hardness
 in
 Information Processing Letters
 volume
 115
 issue
 2
 pages
 82  86
 publisher
 Elsevier
 external identifiers

 wos:000346225300002
 scopus:84911934859
 ISSN
 00200190
 DOI
 10.1016/j.ipl.2014.07.003
 language
 English
 LU publication?
 yes
 id
 2f9ac86d5e354e5f9c205672a10ca2fb (old id 4941538)
 date added to LUP
 20150127 16:45:48
 date last changed
 20180107 06:52:04
@article{2f9ac86d5e354e5f9c205672a10ca2fb, abstract = {We study the complexity of detecting monomials with special properties in the sumproduct 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 first result is a randomized FPT algorithm for detection of a monomial having at least k distinct variables, parametrized with respect to k. For a more restricted class of circuits, we can also provide a deterministic FPT algorithm for detection of a monomial having at most k distinct variables parametrized by the degree of the polynomial represented by the input circuit. 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. (C) 2014 Elsevier B.V. All rights reserved.}, author = {Floderus, Peter and Lingas, Andrzej and Persson, Mia and Sledneu, Dzmitry}, issn = {00200190}, keyword = {Algorithms,Polynomial,Monomial,Arithmetic circuit,Parametrized,complexity,Approximation hardness}, language = {eng}, number = {2}, pages = {8286}, publisher = {Elsevier}, series = {Information Processing Letters}, title = {Detecting monomials with k distinct variables}, url = {http://dx.doi.org/10.1016/j.ipl.2014.07.003}, volume = {115}, year = {2015}, }