Dichotomy for Holant\(^\ast\) problems on the Boolean domain
type: Item
instance of: scholarly article
title: Dichotomy for Holant\(^\ast\) problems on the Boolean domain
zbMATH Open document ID: 1503.68199
author: Jin-Yi Cai
author: Pinyan Lu
author: Mingji Xia
published in: Theory of Computing Systems
publication date: 2021-06-11T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R07
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 7357729
zbMATH Keywords: \#P-hardness
zbMATH Keywords: polynomial-time algorithms
zbMATH Keywords: dichotomy theorems
zbMATH Keywords: Holant problems
zbMATH Keywords: constraint satisfaction problems
zbMATH Keywords: edge coloring models
MaRDI profile type: Publication
OpenAlex ID: W3036972148
cites work: A New Holant Dichotomy Inspired by Quantum Computation
cites work: Q5002678
cites work: Q3324796
cites work: The complexity of the counting constraint satisfaction problem
cites work: The complexity of weighted and unweighted \(\#\)CSP
cites work: The complexity of partition functions
cites work: Complexity Dichotomies for Counting Problems
cites work: Graph homomorphisms with complex values: a dichotomy theorem
cites work: Holographic algorithms: from art to science
cites work: Q5365150
cites work: Dichotomy for Holant Problems with a Function on Domain Size 3
cites work: Q4608007
cites work: Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
cites work: Holant problems and counting CSP
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: The Complexity of Approximating Bounded-Degree Boolean #CSP
cites work: The Complexity of Weighted Boolean #CSP
cites work: An approximation trichotomy for Boolean \#CSP
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4521549
cites work: On the complexity of \#CSP
cites work: Reflection positivity, rank connectivity, and homomorphism of graphs
cites work: A Complexity Dichotomy for Partition Functions with Mixed Signs
cites work: Approximating the Partition Function of the Ferromagnetic Potts Model
cites work: On the complexity of H-coloring
cites work: Beitrag zur Theorie des Ferromagnetismus
cites work: Polynomial-Time Approximation Algorithms for the Ising Model
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5601344
cites work: On the Structure of Polynomial Time Reducibility
cites work: Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
cites work: Q5111359
cites work: Operations with structures
cites work: Markov chain decomposition for convergence rate analysis
cites work: Q5485625
cites work: Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
cites work: The complexity of satisfiability problems
cites work: Edge coloring models and reflection positivity
cites work: Dimer problem in statistical mechanics-an exact result
cites work: Quantum Circuits That Can Be Simulated Classically in Polynomial Time
cites work: Holographic Algorithms
cites work: Q3140234
cites work: The Spontaneous Magnetization of a Two-Dimensional Ising Model
cites work: Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
DOI: 10.1007/S00224-020-09983-8
description: scientific article; zbMATH DE number 7357729