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; \#P; counting problems; dichotomy theorem; holographic algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

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