The computational complexity of Holant problems on 3-regular graphs

DOI10.1016/j.tcs.2023.114256MaRDI QIDQ6199389

Peng Yang, Zhiguo Fu, Yu-An Huang

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexitydichotomyHolant problemsSLOCC

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• The complexity of complex weighted Boolean \#CSP
• The complexity of weighted and unweighted \(\#\)CSP
• Holographic algorithms by Fibonacci gates
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• The complexity of partition functions
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Holographic Algorithms
• The Complexity of Boolean Holant Problems with Nonnegative Weights
• Complexity Dichotomies for Counting Problems
• Complexity of Counting CSP with Complex Weights
• Holant problems and counting CSP
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• The complexity of the counting constraint satisfaction problem
• The Complexity of Symmetric Boolean Parity Holant Problems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem

This page was built for publication: The computational complexity of Holant problems on 3-regular graphs