A Complete Dichotomy Rises from the Capture of Vanishing Signatures

DOI10.1137/15M1049798zbMath1350.68133arXiv1204.6445MaRDI QIDQ2817798

Heng Guo, Jin-Yi Cai, Tyson Williams

Publication date: 2 September 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.6445

zbMATH Keywords

computational complexity\#Pcounting problemsdichotomy theoremholographic algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On blockwise symmetric matchgate signatures and higher domain \#CSP, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Block interpolation: a framework for tight exponential-time counting complexity, Random cluster dynamics for the Ising model is rapidly mixing, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Zeros and approximations of holant polynomials on the complex plane, The Complexity of Boolean Holant Problems with Nonnegative Weights, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, Approximability of the complementarily symmetric Holant problems on cubic graphs, Complexity classification of the eight-vertex model, Unnamed Item, 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, The complexity of planar Boolean \#CSP with complex weights, Unnamed Item, Clifford gates in the Holant framework, 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, FKT is not universal -- a planar holant dichotomy for symmetric constraints, The complexity of counting \(\mathrm{CSP}^d\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• A computational proof of complexity of some restricted counting problems
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• Spin systems on \(k\)-regular graphs with complex edge functions
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On the complexity of H-coloring
• Holographic algorithms beyond matchgates
• Complexity of generalized satisfiability counting problems
• Holographic reduction, interpolation and hardness
• Holographic algorithms by Fibonacci gates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• On the complexity of #CSP
• Computational Complexity of Holant Problems
• Holant Problems for Regular Graphs with Complex Edge Functions
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• Simulating Quantum Computation by Contracting Tensor Networks
• The Complexity of Weighted Boolean #CSP
• Tensor Geometry
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Codes on graphs: normal realizations
• Holant problems and counting CSP
• Classification of a Class of Counting Problems Using Holographic Reductions
• 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
• A complete dichotomy rises from the capture of vanishing signatures
• Operations with structures
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• The Complexity of Symmetric Boolean Parity Holant Problems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem