Dichotomy for Holant\(^\ast\) problems on the Boolean domain

DOI10.1007/s00224-020-09983-8zbMath1503.68199OpenAlexW3036972148MaRDI QIDQ2032295

Jin-Yi Cai, Mingji Xia, Pinyan Lu

Publication date: 11 June 2021

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.194.640

zbMATH Keywords

constraint satisfaction problemspolynomial-time algorithmsdichotomy theoremsHolant problems\#P-hardnessedge coloring models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items

Complexity classification of the eight-vertex model, FKT is not universal -- a planar holant dichotomy for symmetric constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of weighted and unweighted \(\#\)CSP
• Holographic algorithms: from art to science
• An approximation trichotomy for Boolean \#CSP
• On the complexity of H-coloring
• Markov chain decomposition for convergence rate analysis
• Complexity of generalized satisfiability counting problems
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• On the complexity of #CSP
• The statistics of dimers on a lattice
• The Complexity of Approximating Bounded-Degree Boolean #CSP
• Polynomial-Time Approximation Algorithms for the Ising Model
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Edge coloring models and reflection positivity
• The Complexity of Weighted Boolean #CSP
• On the Structure of Polynomial Time Reducibility
• Complexity Dichotomies for Counting Problems
• Beitrag zur Theorie des Ferromagnetismus
• A New Holant Dichotomy Inspired by Quantum Computation
• Holant problems and counting CSP
• Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
• Dimer problem in statistical mechanics-an exact result
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems
• Operations with structures
• Dichotomy for Holant Problems with a Function on Domain Size 3
• The Spontaneous Magnetization of a Two-Dimensional Ising Model
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem