The Complexity of Boolean Holant Problems with Nonnegative Weights
From MaRDI portal
Publication:4571918
DOI10.1137/17M113304XzbMath1397.68105OpenAlexW2807924989MaRDI QIDQ4571918
Publication date: 4 July 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m113304x
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Zero-freeness and approximation of real Boolean Holant problems, Approximability of the complementarily symmetric Holant problems on cubic graphs, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, Complexity classification of the eight-vertex model, The computational complexity of Holant problems on 3-regular graphs, Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS, Dichotomy result on 3-regular bipartite non-negative functions, Dichotomy result on 3-regular bipartite non-negative functions, FKT is not universal -- a planar holant dichotomy for symmetric constraints, The complexity of counting \(\mathrm{CSP}^d\)
Cites Work
- A dichotomy for real weighted Holant problems
- The complexity of complex weighted Boolean \#CSP
- The complexity of weighted and unweighted \(\#\)CSP
- The complexity of weighted Boolean \#CSP with mixed signs
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Holographic algorithms beyond matchgates
- Complexity of generalized satisfiability counting problems
- Valiant's holant theorem and matchgate tensors
- The complexity of partition functions
- A Complete Dichotomy Rises from the Capture of Vanishing Signatures
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- Computational Complexity of Holant Problems
- Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Holographic Algorithms
- On counting homomorphisms to directed acyclic graphs
- The Complexity of Weighted Boolean #CSP
- On the Structure of Polynomial Time Reducibility
- Complexity of Counting CSP with Complex Weights
- Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
- A New Holant Dichotomy Inspired by Quantum Computation
- Holant problems and counting CSP
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- The complexity of the counting constraint satisfaction problem
- Operations with structures
- The Complexity of Symmetric Boolean Parity Holant Problems
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
- Unnamed Item
- Unnamed Item
- Unnamed Item