Holant problems for 3-regular graphs with complex edge functions

DOI10.1007/S00224-016-9671-7zbMATH Open1350.68151OpenAlexW2112310806MaRDI QIDQ315538FDOQ315538

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/

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

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)

Cites Work

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

Cited In (19)

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

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)