Approximability of the complementarily symmetric Holant problems on cubic graphs

DOI10.1016/J.TCS.2023.114140MaRDI QIDQ6076358zbMATH OpenOpenAlexFDO

Authors Yuqiao He, Guoliang Qiu, Chihao Zhang

Publication date 21 September 2023

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

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114140

zbMATH Keywords

approximate countingholantMCMC

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A complete dichotomy rises from the capture of vanishing signatures
• An effective dichotomy for the counting constraint satisfaction problem
• Approximability of the eight-vertex model
• Approximability of the Six-vertex Model
• Approximate counting via correlation decay in spin systems
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Canonical Paths for MCMC: from Art to Science
• Complexity Dichotomies for Counting Problems
• Complexity of counting CSP with complex weights
• Correlation decay up to uniqueness in spin systems
• Holographic Algorithms
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• The complexity of Boolean Holant problems with nonnegative weights
• The complexity of the counting constraint satisfaction problem
• Zero-freeness and approximation of real Boolean Holant problems
• Zeros of Holant Problems

Cited in

(2)

• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• On approximation of asymmetric separators of the n-cube

This page was built for publication: Approximability of the complementarily symmetric Holant problems on cubic graphs

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