Holographic Algorithms
From MaRDI portal
Publication:3532577
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
05A15: Exact enumeration problems, generating functions
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W01: General topics in the theory of algorithms
Related Items
The Complexity of Boolean Holant Problems with Nonnegative Weights, The 1-2 model, Unnamed Item, Unnamed Item, Unnamed Item, Counting Small Induced Subgraphs Satisfying Monotone Properties, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, On the Complexity of Holant Problems, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, 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, Gauging variational inference, Gauges, loops, and polynomials for partition functions of graphical models, Perfect matchings, rank of connection tensors and graph homomorphisms, Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields, 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, Undirected determinant and its complexity, The computational complexity of Holant problems on 3-regular graphs, A dichotomy for real weighted Holant problems, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Holant problems for 3-regular graphs with complex edge functions, The complexity of complex weighted Boolean \#CSP, A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs, Counting the number of perfect matchings in \(K_{5}\)-free graphs, \(P\) versus \(NP\) and geometry, On the complexity of generalized chromatic polynomials, 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, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Some observations on holographic algorithms, On blockwise symmetric matchgate signatures and higher domain \#CSP, Block interpolation: a framework for tight exponential-time counting complexity, On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions, Holographic algorithms beyond matchgates, Complexity classification of the six-vertex model, Clifford gates in the Holant framework, Holographic reduction, interpolation and hardness, Holographic algorithms by Fibonacci gates, Holographic algorithms without matchgates, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, The complexity of planar Boolean \#CSP with complex weights, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, Parameterized counting of partially injective homomorphisms, FKT is not universal -- a planar holant dichotomy for symmetric constraints, The complexity of counting \(\mathrm{CSP}^d\), Zero-freeness and approximation of real Boolean Holant problems, Zeros and approximations of holant polynomials on the complex plane, Evaluations of Tutte polynomials of regular graphs, Counting degree-constrained subgraphs and orientations, Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS, Free fermions behind the disguise, Holographic algorithms on bases of rank 2, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin, Counting edge-injective homomorphisms and matchings on restricted graph classes, Mixing time of Markov chains for the 1-2 model, Functional clones and expressibility of partition functions, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Progress in Complexity of Counting Problems, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
