On the relative complexity of approximate counting problems

DOI10.1007/3-540-44436-X_12MaRDI QIDQ2753731zbMATH OpenFDO

Authors Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum

Publication date 6 January 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/61130/7/WRAP_cs-rr-370.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• The relative complexity of approximate counting problems
• On the parameterized complexity of approximate counting
• Approximate counting and NP search problems
• The relative exponential time complexity of approximate counting satisfying assignments
• The relative exponential time complexity of approximate counting satisfying assignments
• scientific article; zbMATH DE number 1979521
• Randomized Approximations of Parameterized Counting Problems
• Approximate counting with m counters: A detailed analysis
• The Parameterized Complexity of Counting Problems
• Approximate counting with \(m\) counters: a probabilistic analysis

Cited in

(34)

• On the complexity of approximating the Hadwiger number
• On relationships between approximate and probabilistic complexity classes
• The complexity of error metrics
• The relative complexity of approximate counting problems
• The complexity of counting problems
• Majorizing estimators and the approximation of \#P-complete problems
• The relative exponential time complexity of approximate counting satisfying assignments
• Descriptive Complexity of approximate counting CSPs
• Polynomial Space Counting Problems
• On the approximation complexity hierarchy
• The relative exponential time complexity of approximate counting satisfying assignments
• Rényi entropies as a measure of the complexity of counting problems
• Approximately Counting Locally-Optimal Structures
• On Approximation Algorithms for # P
• scientific article; zbMATH DE number 3954144 (Why is no real title available?)
• scientific article; zbMATH DE number 4064488 (Why is no real title available?)
• scientific article; zbMATH DE number 4066859 (Why is no real title available?)
• scientific article; zbMATH DE number 1057883 (Why is no real title available?)
• Counting complexity
• Approximate counting with m counters: A detailed analysis
• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• scientific article; zbMATH DE number 7075922 (Why is no real title available?)
• Approximate Counting CSP Seen from the Other Side
• Approximate counting and NP search problems
• Fine-Grained Reductions from Approximate Counting to Decision
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• Approximately counting paths and cycles in a graph
• On the parameterized complexity of approximate counting
• Efficient deterministic approximate counting for low-degree polynomial threshold functions
• Completeness results for counting problems with easy decision
• Approximate Counting with Deterministic Guarantees for Affinity Computation
• On the Complexity of Approximate Sum of Sorted List
• Polynomial-time algorithms for multimarginal optimal transport problems with structure
• A refined graph container lemma and applications to the hard-core model on bipartite expanders

This page was built for publication: On the relative complexity of approximate counting problems

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