On the Complexity of Holant Problems
From MaRDI portal
Publication:4993599
DOI10.4230/DFU.Vol7.15301.159zbMath1482.68108OpenAlexW2592944259MaRDI QIDQ4993599
Publication date: 15 June 2021
Full work available at URL: https://dblp.uni-trier.de/db/conf/dagstuhl/dfu7.html#GuoL17
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- A dichotomy for real weighted Holant problems
- Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
- The complexity of complex weighted Boolean \#CSP
- A computational proof of complexity of some restricted counting problems
- The complexity of computing the permanent
- Holographic algorithms: from art to science
- Spin systems on \(k\)-regular graphs with complex edge functions
- General factors of graphs
- The linear delta-matroid parity problem
- Expressiveness of matchgates.
- Complexity of generalized satisfiability counting problems
- Holographic reduction, interpolation and hardness
- Holographic algorithms by Fibonacci gates
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- The statistics of dimers on a lattice
- FPTAS for Counting Weighted Edge Covers
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Computational Complexity of Holant Problems
- Holant Problems for Regular Graphs with Complex Edge Functions
- Polynomial-Time Approximation Algorithms for the Ising Model
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Approximating the Permanent
- Reflection positivity, rank connectivity, and homomorphism of graphs
- On Planar Boolean CSP
- Holographic Algorithms
- On counting homomorphisms to directed acyclic graphs
- The Complexity of Enumeration and Reliability Problems
- Tensor Geometry
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Canonical Paths for MCMC: from Art to Science
- Even Delta-Matroids and the Complexity of Planar Boolean CSPs
- FPTAS for Weighted Fibonacci Gates and Its Applications
- Holant problems and counting CSP
- Classification of a Class of Counting Problems Using Holographic Reductions
- Dimer problem in statistical mechanics-an exact result
- Paths, Trees, and Flowers
- A Simple FPTAS for Counting Edge Covers
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- The complexity of satisfiability problems
- Mathematical Foundations of Computer Science 2003
- A complete dichotomy rises from the capture of vanishing signatures
- Maximum matching and a polyhedron with 0,1-vertices
- Dichotomy for Holant Problems with a Function on Domain Size 3
- Fanout limitations on constraint systems
This page was built for publication: On the Complexity of Holant Problems
