Holographic algorithms: from art to science
From MaRDI portal
Publication:619900
DOI10.1016/j.jcss.2010.06.005zbMath1214.68170OpenAlexW2076090007MaRDI QIDQ619900
Publication date: 18 January 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.005
Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (31)
Counting Homomorphisms to Square-Free Graphs, Modulo 2 ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ Counting degree-constrained subgraphs and orientations ⋮ Holographic reduction, interpolation and hardness ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ The complexity of complex weighted Boolean \#CSP ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ Holographic algorithms on domains of general size ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs ⋮ On the Complexity of Holant Problems ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems ⋮ Approximate counting for complex-weighted Boolean constraint satisfaction problems ⋮ Holographic algorithms on bases of rank 2 ⋮ Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Clifford gates in the Holant framework ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ Parameterized counting of partially injective homomorphisms ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Penny-packing and two-dimensional codes ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kneser's conjecture, chromatic number, and homotopy
- On the theory of matchgate computations
- Basis collapse in holographic algorithms
- On symmetric signatures in holographic algorithms
- Holographic algorithms: the power of dimensionality resolved
- On theory and applications of BIB designs with repeated blocks
- Expressiveness of matchgates.
- A combinatorical proof of Kneser's conjecture
- Valiant's holant theorem and matchgate tensors
- Computational complexity of counting problems on 3-regular planar graphs
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- The statistics of dimers on a lattice
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Signature Theory in Holographic Algorithms
- Planar Formulae and Their Uses
- On the Structure oft-Designs
- Incidence Matrices of Subsets—A Rank Formula
- Dimer problem in statistical mechanics-an exact result
- The complexity of theorem-proving procedures
- Matrices and matroids for systems analysis
This page was built for publication: Holographic algorithms: from art to science
