Advanced

Detecting monomials with k distinct variables

Floderus, Peter LU ; Lingas, Andrzej LU ; Persson, Mia LU and Sledneu, Dzmitry LU (2015) In Information Processing Letters 115(2). p.82-86
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.... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
0020-0190
DOI
10.1016/j.ipl.2014.07.003
language
English
LU publication?
yes
id
2f9ac86d-5e35-4e5f-9c20-5672a10ca2fb (old id 4941538)
date added to LUP
2015-01-27 16:45:48
date last changed
2017-08-27 04:35:43
@article{2f9ac86d-5e35-4e5f-9c20-5672a10ca2fb,
  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.},
  author       = {Floderus, Peter and Lingas, Andrzej and Persson, Mia and Sledneu, Dzmitry},
  issn         = {0020-0190},
  keyword      = {Algorithms,Polynomial,Monomial,Arithmetic circuit,Parametrized,complexity,Approximation hardness},
  language     = {eng},
  number       = {2},
  pages        = {82--86},
  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},
}