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