Detecting monomials with \(k\) distinct variables

DOI10.1016/j.ipl.2014.07.003zbMath1302.68312OpenAlexW1966623661MaRDI QIDQ477587

Andrzej Lingas, Dzmitry Sledneu, Mia Persson, Peter Floderus

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

algorithmsmonomialpolynomialarithmetic circuitparametrized complexityapproximation hardness

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Secluded connectivity problems
• On r-Simple k-Path
• A threshold of ln n for approximating set cover
• Faster Algebraic Algorithms for Path and Packing Problems
• Limits and Applications of Group Algebras for Parameterized Problems
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Monomial Testing and Applications

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