Holant problems for 3-regular graphs with complex edge functions

DOI10.1007/S00224-016-9671-7MaRDI QIDQ315538zbMATH OpenOpenAlexFDO

Authors Michael Kowalczyk, Jin-Yi Cai

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)

Recommendations

• Holant problems for regular graphs with complex edge functions
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• Dichotomy result on 3-regular bipartite non-negative functions
• Computational complexity of Holant problems

Cites work

• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• A computational proof of complexity of some restricted counting problems
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Classification of a Class of Counting Problems Using Holographic Reductions
• Computational complexity of counting problems on 3-regular planar graphs
• Graph homomorphisms with complex values: a dichotomy theorem
• Holant problems for regular graphs with complex edge functions
• Holographic Algorithms
• Holographic algorithms by Fibonacci gates
• Holographic algorithms: from art to science
• Holographic reduction, interpolation and hardness
• On counting homomorphisms to directed acyclic graphs
• On the complexity of H-coloring
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Spin systems on \(k\)-regular graphs with complex edge functions
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity of counting in sparse, regular, and planar graphs
• The complexity of partition functions

Cited in

(19)

• A computational proof of complexity of some restricted counting problems
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• Holant problems for regular graphs with complex edge functions
• Restricted Holant dichotomy on domain sizes 3 and 4
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Computational complexity of counting problems on 3-regular planar graphs
• A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
• Restricted Holant dichotomy on domains 3 and 4
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• Spin systems on \(k\)-regular graphs with complex edge functions
• Spin systems on graphs with complex edge functions and specified degree regularities
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Approximating the chromatic polynomial is as hard as computing it exactly
• 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
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)

This page was built for publication: Holant problems for 3-regular graphs with complex edge functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q315538)