Holant problems for 3-regular graphs with complex edge functions

DOI10.1007/s00224-016-9671-7zbMath1350.68151OpenAlexW2112310806MaRDI QIDQ315538

Jin-Yi Cai, Michael Kowalczyk

Publication date: 21 September 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2482/

zbMATH Keywords

computational complexitycounting problemsdichotomy theoremsHolant problemsholographic algorithms

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

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, Approximating the chromatic polynomial is as hard as computing it exactly, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, Dichotomy result on 3-regular bipartite non-negative functions, Dichotomy result on 3-regular bipartite non-negative functions, Bipartite 3-regular counting problems with mixed signs, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• On the complexity of H-coloring
• Holographic reduction, interpolation and hardness
• Holographic algorithms by Fibonacci gates
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of partition functions
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Holant Problems for Regular Graphs with Complex Edge Functions
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• The Complexity of Enumeration and Reliability Problems
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Classification of a Class of Counting Problems Using Holographic Reductions
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem