The Complexity of Weighted Boolean #CSP
From MaRDI portal
Publication:3642870
DOI10.1137/070690201zbMath1191.68351arXiv0704.3683OpenAlexW3124201190WikidataQ56323856 ScholiaQ56323856MaRDI QIDQ3642870
Martin Dyer, Leslie Ann Goldberg, Mark R. Jerrum
Publication date: 6 November 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0704.3683
Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Coloring of graphs and hypergraphs (05C15)
Related Items
Tractability in constraint satisfaction problems: a survey, The complexity of weighted Boolean \#CSP with mixed signs, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Classification of a Class of Counting Problems Using Holographic Reductions, The Complexity of Boolean Holant Problems with Nonnegative Weights, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, The complexity of complex weighted Boolean \#CSP, The complexity of weighted counting for acyclic conjunctive queries, The complexity of approximating bounded-degree Boolean \(\#\)CSP, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, The complexity of weighted and unweighted \(\#\)CSP, Holographic algorithms beyond matchgates, A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS, A structured view on weighted counting with relations to counting, quantum computation and applications, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, Counting Constraint Satisfaction Problems., A collapse theorem for holographic algorithms with matchgates on domain size at most 4, Spin systems on \(k\)-regular graphs with complex edge functions, 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, The complexity of planar Boolean \#CSP with complex weights, An approximation trichotomy for Boolean \#CSP, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, The Complexity of Symmetric Boolean Parity Holant Problems, The complexity of approximating conservative counting CSPs, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin, Definability for model counting, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, The complexity of counting homomorphisms to cactus graphs modulo 2, Approximate Counting via Correlation Decay in Spin Systems, Classical simulation of quantum circuits by half Gauss sums, A dichotomy for real weighted Holant problems
