A dichotomy for real weighted Holant problems

DOI10.1007/s00037-015-0118-3zbMath1336.68099OpenAlexW2244287056MaRDI QIDQ260401

Pinyan Lu, Sangxia Huang

Publication date: 21 March 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0118-3

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, Counting Small Induced Subgraphs Satisfying Monotone Properties, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, The Complexity of Boolean Holant Problems with Nonnegative Weights, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, Complexity classification of the eight-vertex model, Unnamed Item, A strengthening and an efficient implementation of Alon-Tarsi list coloring method, The computational complexity of Holant problems on 3-regular graphs, Holographic algorithms beyond matchgates, Complexity classification of the six-vertex model, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, On the Complexity of Holant Problems, The complexity of planar Boolean \#CSP with complex weights, Clifford gates in the Holant framework, Parameterized counting of partially injective homomorphisms, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, FKT is not universal -- a planar holant dichotomy for symmetric constraints, The complexity of counting \(\mathrm{CSP}^d\), A dichotomy for real weighted Holant problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• A computational proof of complexity of some restricted counting problems
• The complexity of computing the permanent
• 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
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• On the number of Eulerian orientations of a graph
• Holographic algorithms by Fibonacci gates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of counting Eulerian tours in 4-regular graphs
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• On the complexity of #CSP
• Integer Programming with a Fixed Number of Variables
• Holant Problems for Regular Graphs with Complex Edge Functions
• Corrigendum: The complexity of counting graph homomorphisms
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Holographic Algorithms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On counting homomorphisms to directed acyclic graphs
• Some Observations on Holographic Algorithms
• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• 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
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On the computational complexity of the Jones and Tutte polynomials
• Beitrag zur Theorie des Ferromagnetismus
• Holant problems and counting CSP
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• Automata, Languages and Programming
• The Computational Complexity of Tutte Invariants for Planar Graphs
• A complete dichotomy rises from the capture of vanishing signatures
• 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