The Complexity of Weighted Boolean #CSP
From MaRDI portal
Publication:3642870
DOI10.1137/070690201zbMath1191.68351arXiv0704.3683WikidataQ56323856 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
68Q25: Analysis of algorithms and problem complexity
68T27: Logic in artificial intelligence
05C15: Coloring of graphs and hypergraphs
Related Items
The Complexity of Boolean Holant Problems with Nonnegative Weights, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, Counting Constraint Satisfaction Problems., Classification of a Class of Counting Problems Using Holographic Reductions, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, The Complexity of Symmetric Boolean Parity Holant Problems, Approximate Counting via Correlation Decay in Spin Systems, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, A dichotomy for real weighted Holant problems, Tractability in constraint satisfaction problems: a survey, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, The complexity of complex weighted Boolean \#CSP, The complexity of weighted counting for acyclic conjunctive queries, The complexity of weighted and unweighted \(\#\)CSP, A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs, 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, The complexity of approximating conservative counting CSPs, The complexity of weighted Boolean \#CSP with mixed signs, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, An approximation trichotomy for Boolean \#CSP, Holographic algorithms beyond matchgates, The complexity of approximating bounded-degree Boolean \(\#\)CSP, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, The complexity of planar Boolean \#CSP with complex weights, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, Classical simulation of quantum circuits by half Gauss sums, 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, Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems, 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, The complexity of counting homomorphisms to cactus graphs modulo 2
