On the parameterized complexity of approximate counting

DOI10.1051/ita/2011007zbMath1234.68121OpenAlexW2051058708MaRDI QIDQ5198932

Juan Andrés Montoya

Publication date: 10 August 2011

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/221979

zbMATH Keywords

computational complexityparameterized complexityapproximate countingcounting problems

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 (2)

Compactors for parameterized counting problems ⋮ Parameterized random complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The parameterized complexity of probability amplification
• BPP and the polynomial hierarchy
• PRIMES is in P
• Parametrized complexity theory.
• PP is as Hard as the Polynomial-Time Hierarchy
• 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: On the parameterized complexity of approximate counting