Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin

DOI10.1016/j.jcss.2019.12.003zbMath1435.68221arXiv1804.04993OpenAlexW2796897474WikidataQ126469753 ScholiaQ126469753MaRDI QIDQ2301362

Stanislav Živný, Miriam Backens, Leslie Ann Goldberg, Colin McQuillan, Andrei A. Bulatov

Publication date: 24 February 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.04993

zbMATH Keywords

constraint satisfactionapproximate countingferromagnetic two-spinweak conservativity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Statistical mechanics of magnetic materials (82D40) Computational aspects of satisfiability (68R07)

Related Items (1)

Counting Small Induced Subgraphs Satisfying Monotone Properties

Cites Work

• Unnamed Item
• The complexity of complex weighted Boolean \#CSP
• The complexity of approximating conservative counting CSPs
• Structure identification of Boolean relations and plain bases for co-clones
• An approximation trichotomy for Boolean \#CSP
• The relative complexity of approximate counting problems
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• Functional clones and expressibility of partition functions
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The Complexity of Ferromagnetic Two-spin Systems with External Fields
• Approximating the Permanent
• The Complexity of Ferromagnetic Ising with Local Fields
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• Minimizing a Submodular Function on a Lattice
• The computational complexity of two‐state spin systems
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• Correlation Decay up to Uniqueness in Spin Systems

This page was built for publication: Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin