Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
type: Item
instance of: scholarly article
title: Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
zbMATH Open document ID: 1370.68117
DOI: 10.1137/16M1073984
author: Jin-Yi Cai
author: Pinyan Lu
author: Mingji Xia
published in: SIAM Journal on Computing
publication date: 2017-05-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/1008.0683
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6724225
zbMATH Keywords: holographic algorithms
zbMATH Keywords: counting problems
zbMATH Keywords: \#P
zbMATH Keywords: dichotomy theorems
MaRDI profile type: Publication
arXiv ID: 1008.0683
cites work: Q3324796
cites work: The Complexity of the Counting Constraint Satisfaction Problem
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: Automata, Languages and Programming
cites work: The complexity of partition functions
cites work: Graph homomorphisms with complex values: a dichotomy theorem
cites work: Some Results on Matchgates and Holographic Algorithms
cites work: Valiant's holant theorem and matchgate tensors
cites work: Q3191606
cites work: A complete dichotomy rises from the capture of vanishing signatures
cites work: From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
cites work: Q3549638
cites work: Basis collapse in holographic algorithms
cites work: Q3579392
cites work: On symmetric signatures in holographic algorithms
cites work: A Computational Proof of Complexity of Some Restricted Counting Problems
cites work: Holant problems and counting CSP
cites work: Tensor Geometry
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4521549
cites work: Reflection positivity, rank connectivity, and homomorphism of graphs
cites work: The complexity of symmetric Boolean parity Holant problems
cites work: Beitrag zur Theorie des Ferromagnetismus
cites work: Statistical mechanics, three-dimensionality and NP-completeness
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: Classification of a Class of Counting Problems Using Holographic Reductions
cites work: Holant Problems for Regular Graphs with Complex Edge Functions
cites work: Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
cites work: Q5485625
cites work: Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
cites work: Dimer problem in statistical mechanics-an exact result
cites work: The complexity of counting in sparse, regular, and planar graphs
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Expressiveness of matchgates.
cites work: Quantum Circuits That Can Be Simulated Classically in Polynomial Time
cites work: Holographic Algorithms
cites work: Q3140234
cites work: Computational complexity of counting problems on 3-regular planar graphs
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
description: scientific article; zbMATH DE number 6724225