The relative complexity of approximate counting problems
From MaRDI portal
Publication:1879247
DOI10.1007/s00453-003-1073-yzbMath1138.68424OpenAlexW2177243619WikidataQ56323980 ScholiaQ56323980MaRDI QIDQ1879247
Leslie Ann Goldberg, Catherine Greenhill, Martin Dyer, Mark R. Jerrum
Publication date: 22 September 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/61130/7/WRAP_cs-rr-370.pdf
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, Completeness Results for Counting Problems with Easy Decision, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, The complexity of counting locally maximal satisfying assignments of Boolean CSPs, Approximately counting locally-optimal structures, Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard, Approximately Counting Locally-Optimal Structures, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, Completeness, approximability and exponential time results for counting problems with easy decision version, Zero-freeness and approximation of real Boolean Holant problems, A Graph Polynomial for Independent Sets of Bipartite Graphs, Mixing of the Glauber dynamics for the ferromagnetic Potts model, An FPTAS for the hardcore model on random regular bipartite graphs, On the concentration of the number of solutions of random satisfiability formulas, Zeros and approximations of holant polynomials on the complex plane, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, Algorithmic Pirogov-Sinai theory, On the connection between interval size functions and path counting, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, The Complexity of Approximately Counting Tree Homomorphisms, The complexity of approximating bounded-degree Boolean \(\#\)CSP, Counting vertices of integral polytopes defined by facets, Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures, Approximately counting independent sets in bipartite graphs via graph containers, Sampling from the low temperature Potts model through a Markov chain on flows, The complexity of weighted and unweighted \(\#\)CSP, The Complexity of Aggregates over Extractions by Regular Expressions, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, A complexity classification of spin systems with an external field, Approximation Algorithms for the Random Field Ising Model, The complexity of counting Eulerian tours in 4-regular graphs, The complexity of approximately counting stable roommate assignments, The complexity of approximately counting stable matchings, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, Unnamed Item, A structured view on weighted counting with relations to counting, quantum computation and applications, Counting independent sets in cocomparability graphs, Counting Constraint Satisfaction Problems., Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, Inapproximability of the Tutte polynomial, Boolean max-co-clones, Algorithms for #BIS-Hard Problems on Expander Graphs, Faster exponential-time algorithms for approximately counting independent sets, Dualization in lattices given by ordered sets of irreducibles, Approximately counting paths and cycles in a graph, Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems, Approximate counting for complex-weighted Boolean constraint satisfaction problems, Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems, An approximation trichotomy for Boolean \#CSP, Counting substrate cycles in topologically restricted metabolic networks, A fixed-parameter perspective on \#BIS, Counting independent sets in graphs with bounded bipartite pathwidth, Unnamed Item, Unnamed Item, Unnamed Item, Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard, The complexity of approximating conservative counting CSPs, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin, Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, The Complexity of Counting Surjective Homomorphisms and Compactions, Counting Weighted Independent Sets beyond the Permanent, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Unnamed Item, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, Hand-waving and interpretive dance: an introductory course on tensor networks, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs, The complexity of estimating min-entropy
