Detecting monomials with k distinct variables

DOI10.1016/J.IPL.2014.07.003zbMATH Open1302.68312OpenAlexW1966623661MaRDI QIDQ477587FDOQ477587

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

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

zbMATH Keywords

algorithmsmonomialpolynomialparametrized complexityarithmetic circuitapproximation hardness

Mathematics Subject Classification ID

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

Cites Work

• 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
• Title not available (Why is that?)
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Secluded connectivity problems
• On r-Simple k-Path
• 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)