Holographic Algorithms
From MaRDI portal
complexity classescomputational complexityefficient reductionenumerationgadgetsgenerating interference patternsholographic reductionmany-to-many correspondencespolynomial equationspolynomial time algorithmssolution fragments
Exact enumeration problems, generating functions (05A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) General topics in the theory of algorithms (68W01)
Recommendations
Cited in
(93)- Holographic algorithms: the power of dimensionality resolved
- Some observations on holographic algorithms
- On blockwise symmetric matchgate signatures and higher domain \#CSP
- On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
- Complexity classification of the six-vertex model
- Holographic non-computers
- 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
- 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 dichotomy for real weighted Holant problems
- A complete dichotomy rises from the capture of vanishing signatures
- Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
- Progress in complexity of counting 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
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Holographic algorithms: from art to science
- Holographic algorithms
- The complexity of complex weighted Boolean \#CSP
- A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
- The complexity of Boolean Holant problems with nonnegative weights
- The 1-2 model
- A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
- On the Complexity of Holant Problems
- A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
- Counting problems in parameterized complexity
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
- Tensor network complexity of multilinear maps
- A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
- Automata, Languages and Programming
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Gauging variational inference
- Gauges, loops, and polynomials for partition functions of graphical models
- Perfect matchings, rank of connection tensors and graph homomorphisms
- The complexity of symmetric Boolean parity Holant problems (extended abstract)
- 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
- Holographic data storage. With a foreword by Alstair M. Glass and Mark J. Cardillo
- Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
- \(P\) versus \(NP\) and geometry
- 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
- Holographic algorithms: from art to science
- The computational complexity of Holant problems on 3-regular graphs
- The complexity of counting planar graph homomorphisms of domain size 3
- Restricted Holant dichotomy on domains 3 and 4
- A complexity trichotomy for k-regular asymmetric spin systems with complex edge functions
- Restricted Holant dichotomy on domain sizes 3 and 4
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- On the complexity of generalized chromatic polynomials
- Counting perfect matchings and the eight-vertex model
- From holant to quantum entanglement and back
- Counting degree-constrained orientations
- Fair selection of clearing schemes for kidney exchange markets
- Sub-exponential time lower bounds for \#VC and \#Matching on 3-regular graphs
- Spin systems on k-regular graphs with complex edge functions
- Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
- A combinatorial view of Holant problems on higher domains
- Planar \#CSP equality corresponds to quantum isomorphism -- a Holant viewpoint
- Killing a vortex
- Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
- On the complexity of \#CSP\(^d\)
- Towards a complexity-theoretic dichotomy for TQFT invariants
- Parameterised holant problems
- P-time algorithms for typical \#EO problems
- Matchgate signatures under variable permutations
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
This page was built for publication: Holographic Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3532577)
