The Complexity of Boolean Holant Problems with Nonnegative Weights
type: Item
instance of: scholarly article
title: The Complexity of Boolean Holant Problems with Nonnegative Weights
zbMATH Open document ID: 1397.68105
DOI: 10.1137/17M113304X
author: Jiabao Lin
author: Hanpin Wang
published in: SIAM Journal on Computing
publication date: 2018-07-04T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6898309
zbMATH Keywords: counting complexity
zbMATH Keywords: dichotomy
zbMATH Keywords: Holant
zbMATH Keywords: \(\#\)CSP
MaRDI profile type: Publication
cites work: A New Holant Dichotomy Inspired by Quantum Computation
cites work: The complexity of the counting constraint satisfaction problem
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: The complexity of weighted and unweighted \(\#\)CSP
cites work: The complexity of weighted Boolean \#CSP with mixed signs
cites work: The complexity of partition functions
cites work: Complexity of Counting CSP with Complex Weights
cites work: Graph homomorphisms with complex values: a dichotomy theorem
cites work: Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
cites work: Valiant's holant theorem and matchgate tensors
cites work: Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
cites work: Holographic algorithms beyond matchgates
cites work: A complete dichotomy rises from the capture of vanishing signatures
cites work: Holant problems and counting CSP
cites work: Computational Complexity of Holant Problems
cites work: Q5365150
cites work: The complexity of complex weighted Boolean \#CSP
cites work: Q4608007
cites work: Complexity of generalized satisfiability counting problems
cites work: The Complexity of Weighted Boolean #CSP
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4521549
cites work: An effective dichotomy for the counting constraint satisfaction problem
cites work: Reflection positivity, rank connectivity, and homomorphism of graphs
cites work: A Complexity Dichotomy for Partition Functions with Mixed Signs
cites work: The complexity of symmetric Boolean parity Holant problems
cites work: A dichotomy for real weighted Holant problems
cites work: On the Structure of Polynomial Time Reducibility
cites work: Operations with structures
cites work: Holographic Algorithms
full work available at URL: 17m113304x
OpenAlex ID: W2807924989
Wikidata QID: Q129700436
description: scientific article; zbMATH DE number 6898309