Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
From MaRDI portal
Publication:3179267
DOI10.1137/15M1032314zbMath1356.68094arXiv1012.5659OpenAlexW2567588342MaRDI QIDQ3179267
Xi Chen, Pinyan Lu, Jin-Yi Cai
Publication date: 21 December 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.5659
Related Items
The Complexity of Boolean Holant Problems with Nonnegative Weights, What can be sampled locally?, Complexity classification of the eight-vertex model, The computational complexity of Holant problems on 3-regular graphs, Holographic algorithms beyond matchgates, 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, Dichotomy result on 3-regular bipartite non-negative functions, Bipartite 3-regular counting problems with mixed signs, Dichotomy result on 3-regular bipartite non-negative functions, Bipartite 3-regular counting problems with mixed signs, Approximate Counting via Correlation Decay in Spin Systems, The complexity of counting \(\mathrm{CSP}^d\), A dichotomy for real weighted Holant problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of weighted and unweighted \(\#\)CSP
- Approximation resistant predicates from pairwise independence
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- A new line of attack on the dichotomy conjecture
- On the complexity of H-coloring
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- The complexity of partition functions
- A Complete Dichotomy Rises from the Capture of Vanishing Signatures
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- Holographic Algorithms
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- On counting homomorphisms to directed acyclic graphs
- Conditional Hardness for Approximate Coloring
- Algorithms in Algebraic Number Theory
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- How to Round Any CSP
- CSP gaps and reductions in the lasserre hierarchy
- Holant problems and counting CSP
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- The complexity of the counting constraint satisfaction problem
- The complexity of satisfiability problems
- Complexity of counting CSP with complex weights
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A Simple Algorithm for Mal'tsev Constraints
- Recent Results on the Algebraic Approach to the CSP
- Operations with structures
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Dichotomy for Holant Problems with a Function on Domain Size 3
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
- Principles and Practice of Constraint Programming – CP 2003
