Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Detecting monomials with k distinct variables
Malmö högskola, Faculty of Technology and Society (TS).
2015 (English)In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 115, no 2, p. 82-86Article in journal (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2015. Vol. 115, no 2, p. 82-86
Keywords [en]
Algorithms, Polynomial, Monomial, Arithmetic circuit, Parametrized, complexity, Approximation hardness
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mau:diva-2613DOI: 10.1016/j.ipl.2014.07.003ISI: 000346225300002Scopus ID: 2-s2.0-84911934859Local ID: 19729OAI: oai:DiVA.org:mau-2613DiVA, id: diva2:1399376
Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2024-02-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Persson, Mia

Search in DiVA

By author/editor
Persson, Mia
By organisation
Faculty of Technology and Society (TS)
In the same journal
Information Processing Letters
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 27 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf