The relative complexity of approximate counting problems
From MaRDI portal
Recommendations
Cited in
(89)- Approximately counting independent sets in bipartite graphs via graph containers
- Fine-Grained Reductions from Approximate Counting to Decision
- Approximate Counting CSP Seen from the Other Side
- Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function
- Hardness of identity testing for restricted Boltzmann machines and Potts models
- Approximate Counting with Deterministic Guarantees for Affinity Computation
- Descriptive Complexity of approximate counting CSPs
- Counting constraint satisfaction problems
- Counting weighted independent sets beyond the permanent
- Efficient algorithms for the Potts model on small-set expanders
- On the number of \(k\)-proper connected edge and vertex colorings of graphs
- Approximation Algorithms for the Random Field Ising Model
- Counting on rainbow \(k\)-connections
- Fast algorithms for general spin systems on bipartite expanders
- Algorithms for the ferromagnetic Potts model on expanders
- The Complexity of Aggregates over Extractions by Regular Expressions
- Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- Sampling from the low temperature Potts model through a Markov chain on flows
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- Efficient deterministic approximate counting for low-degree polynomial threshold functions
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
- On the complexity of approximating the Hadwiger number
- Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
- A graph polynomial for independent sets of bipartite graphs
- Faster exponential-time algorithms for approximately counting independent sets
- Spanning tree constrained determinantal point processes are hard to (approximately) evaluate
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Boolean max-co-clones
- Counting independent sets in graphs with bounded bipartite pathwidth
- Completeness, approximability and exponential time results for counting problems with easy decision version
- Zero-freeness and approximation of real Boolean Holant problems
- The complexity of approximately counting stable roommate assignments
- scientific article; zbMATH DE number 7075922 (Why is no real title available?)
- An approximation trichotomy for Boolean \#CSP
- Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
- scientific article; zbMATH DE number 4064488 (Why is no real title available?)
- Approximately counting \(H\)-colorings is \(\#\)BIS-hard
- Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
- Complexity of counting the optimal solutions
- The complexity of counting locally maximal satisfying assignments of Boolean CSPs
- Counting independent sets in cocomparability graphs
- The complexity of approximately counting tree homomorphisms
- The complexity of weighted and unweighted \(\#\)CSP
- The complexity of counting problems
- The complexity of approximately counting stable matchings
- Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
- On the connection between interval size functions and path counting
- Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
- A structured view on weighted counting with relations to counting, quantum computation and applications
- Subtractive reductions and complete problems for counting complexity classes
- scientific article; zbMATH DE number 1759419 (Why is no real title available?)
- Approximately Counting Locally-Optimal Structures
- Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
- scientific article; zbMATH DE number 1670534 (Why is no real title available?)
- The complexity of counting surjective homomorphisms and compactions
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Mixing of the Glauber dynamics for the ferromagnetic Potts model
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- Algorithmic Pirogov-Sinai theory
- Descriptive complexity of \(\#\)P functions
- Approximate counting with \(m\) counters: A detailed analysis
- The complexity of approximating conservative counting CSPs
- Algorithms for \#BIS-hard problems on expander graphs
- Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
- A fixed-parameter perspective on \#BIS
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- On Approximation Algorithms for # P
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- A fixed-parameter perspective on \#BIS
- Inapproximability of the Tutte polynomial
- Counting vertices of integral polytopes defined by facets
- The complexity of estimating min-entropy
- Dualization in lattices given by ordered sets of irreducibles
- Approximately counting paths and cycles in a graph
- A complexity classification of spin systems with an external field
- Counting substrate cycles in topologically restricted metabolic networks
- Approximately counting locally-optimal structures
- On the approximation complexity hierarchy
- On the concentration of the number of solutions of random satisfiability formulas
- Hand-waving and interpretive dance: an introductory course on tensor networks
- Approximate counting and NP search problems
- An FPTAS for the hardcore model on random regular bipartite graphs
- Zeros and approximations of holant polynomials on the complex plane
- Completeness results for counting problems with easy decision
This page was built for publication: 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 Q1879247)
