Holographic Algorithms

DOI10.1137/070682575zbMath1152.05010MaRDI QIDQ3532577

Publication date: 28 October 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

computational complexity enumeration polynomial equations polynomial time algorithms complexity classes holographic reduction gadgets efficient reduction generating interference patterns many-to-many correspondences solution fragments

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)

Related Items

Some observations on holographic algorithms ⋮ Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ Zero-freeness and approximation of real Boolean Holant problems ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Counting degree-constrained subgraphs and orientations ⋮ $P$ versus $NP$ and geometry ⋮ Holographic reduction, interpolation and hardness ⋮ A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation ⋮ The complexity of complex weighted Boolean \#CSP ⋮ Holographic algorithms by Fibonacci gates ⋮ Holographic algorithms without matchgates ⋮ Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields ⋮ From Holant to \#CSP and back: dichotomy for Holant$^{c}$ problems ⋮ Approximability of the complementarily symmetric Holant problems on cubic graphs ⋮ Holographic algorithms on domains of general size ⋮ A complexity trichotomy for $k$-regular asymmetric spin systems using number theory ⋮ Complexity classification of the eight-vertex model ⋮ Polynomial-time solvable $\#$CSP problems via algebraic models and Pfaffian circuits ⋮ Undirected determinant and its complexity ⋮ Unnamed Item ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Unnamed Item ⋮ On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions ⋮ Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$ ⋮ Holographic algorithms beyond matchgates ⋮ Complexity classification of the six-vertex model ⋮ A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs ⋮ Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs ⋮ Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS ⋮ A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory ⋮ On the Complexity of Holant Problems ⋮ The 1-2 model ⋮ Progress in Complexity of Counting Problems ⋮ Counting the number of perfect matchings in $K_{5}$-free graphs ⋮ On the complexity of generalized chromatic polynomials ⋮ Free fermions behind the disguise ⋮ 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 ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Unnamed Item ⋮ Clifford gates in the Holant framework ⋮ Dichotomy for Holant$^\ast$ problems on the Boolean domain ⋮ Parameterized counting of partially injective homomorphisms ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin ⋮ 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 ⋮ The complexity of counting $\mathrm{CSP}^d$ ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices ⋮ Mixing time of Markov chains for the 1-2 model ⋮ Gauging variational inference ⋮ Gauges, loops, and polynomials for partition functions of graphical models ⋮ A dichotomy for real weighted Holant problems ⋮ Functional clones and expressibility of partition functions