The expressibility of functions on the boolean domain, with applications to counting CSPs
From MaRDI portal
Publication:5395728
DOI10.1145/2528401zbMath1281.68131arXiv1108.5288OpenAlexW3125322785WikidataQ56323823 ScholiaQ56323823MaRDI QIDQ5395728
Leslie Ann Goldberg, Martin Dyer, Andrei A. Bulatov, Colin McQuillan, Mark R. Jerrum
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.5288
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Approximation algorithms (68W25)
Related Items
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, Tractability in constraint satisfaction problems: a survey, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, An FPTAS for the hardcore model on random regular bipartite graphs, The Complexity of Approximately Counting Tree Homomorphisms, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, The algebraic structure of the densification and the sparsification tasks for CSPs, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, A complexity classification of spin systems with an external field, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, Counting Constraint Satisfaction Problems., Boolean max-co-clones, Faster exponential-time algorithms for approximately counting independent sets, The complexity of approximating conservative counting CSPs, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Unnamed Item, Functional clones and expressibility of partition functions
