Detecting monomials with k distinct variables

DOI10.1016/J.IPL.2014.07.003MaRDI QIDQ477587zbMATH OpenOpenAlexFDO

Authors Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2014.07.003

zbMATH Keywords

algorithmsapproximation hardnessarithmetic circuitmonomialparametrized complexitypolynomial

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Recommendations

• Algorithms for testing monomials in multivariate polynomials
• The complexity of testing monomials in multivariate polynomials
• Monomial testing and applications
• On testing monomials in multivariate polynomials
• Monomials in arithmetic circuits: complete problems in the counting hierarchy

Cites work

• A threshold of ln n for approximating set cover
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Limits and Applications of Group Algebras for Parameterized Problems
• Monomial testing and applications
• On r-Simple k-Path
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory

Cited in

(3)

• Toward randomized testing of q-monomials in multivariate polynomials
• Algorithms for testing monomials in multivariate polynomials
• Monomial testing and applications

This page was built for publication: Detecting monomials with \(k\) distinct variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477587)