Detecting monomials with k distinct variables

DSpace Repository

Detecting monomials with k distinct variables

Overview

Detailed record

dc.contributor.author Floderus, Peter
dc.contributor.author Lingas, Andrzej
dc.contributor.author Persson, Mia
dc.contributor.author Sledneu, Dzmitry
dc.date.accessioned 2015-11-27T14:46:26Z
dc.date.available 2015-11-27T14:46:26Z
dc.date.issued 2015 en_US
dc.identifier.issn 0020-0190 en_US
dc.identifier.uri http://hdl.handle.net/2043/19729
dc.description.abstract 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 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. en_US
dc.format.extent 5
dc.language.iso eng en_US
dc.publisher Elsevier en_US
dc.subject Algorithms en_US
dc.subject Polynomial en_US
dc.subject Monomial en_US
dc.subject Arithmetic circuit en_US
dc.subject Parametrized en_US
dc.subject complexity en_US
dc.subject Approximation hardness en_US
dc.subject.classification Technology en_US
dc.title Detecting monomials with k distinct variables en_US
dc.type Article, peer reviewed scientific en_US
dc.contributor.department Malmö University. Faculty of Technology and Society
dc.identifier.doi 10.1016/j.ipl.2014.07.003 en_US
dc.subject.srsc Research Subject Categories::TECHNOLOGY en_US
dc.relation.ispartofpublication Information Processing Letters;2
dc.relation.ispartofpublicationvolume 115 en_US
dc.format.ePage 86
dc.format.sPage 82
 Find Full text Files for download

There are no files associated with this item.

This item appears in the following Collection(s)

Overview

Search


Browse

My Account

Statistics