The parameterized complexity of probability amplification

DOI10.1016/j.ipl.2008.06.007zbMath1191.68342OpenAlexW2022281049MaRDI QIDQ975525

Juan Andrés Montoya

Publication date: 9 June 2010

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

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

zbMATH Keywords

computational complexityparameterized complexityprobabilistic classesprobability amplification

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Parameterized random complexity ⋮ Confronting intractability via parameters ⋮ On the parameterized complexity of approximate counting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Parameterized circuit complexity and the \(W\) hierarchy
• Parametrized complexity theory.
• PP is as Hard as the Polynomial-Time Hierarchy
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• Randomized Approximations of Parameterized Counting Problems
• On Approximation Algorithms for # P
• The Complexity of Enumeration and Reliability Problems
• The Parameterized Complexity of Counting Problems

This page was built for publication: The parameterized complexity of probability amplification