Holographic algorithms without matchgates
From MaRDI portal
Exact enumeration problems, generating functions (05A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Special matrices (15B99) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)
Abstract: The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, yields insight into the hierarchy of complexity classes. In particular, the theory produces algebraic tests for a problem to be in the class P. In this article we streamline the implementation of holographic algorithms by eliminating one of the steps in the construction procedure, and generalize their applicability to new signatures. Instead of matchgates, which are weighted graph fragments that replace vertices of a natural bipartite graph G associated to a problem P, our approach uses only only a natural number-of-edges by number-of-edges matrix associated to G. An easy-to-compute multiple of its Pfaffian is the number of solutions to the counting problem. This simplification improves our understanding of the applicability of holographic algorithms, indicates a more geometric approach to complexity classes, and facilitates practical implementations. The generalized applicability arises because our approach allows for new algebraic tests that are different from the "Grassmann-Plucker identities" used up until now. Natural problems treatable by these new methods have been previously considered in a different context, and we present one such example.
Recommendations
Cites work
- A combinatorial Laplacian with vertex weights
- Applications of minor-summation formula. II: Pfaffians and Schur polynomials
- Automata, Languages and Programming
- Basis collapse in holographic algorithms
- Dimer problem in statistical mechanics-an exact result
- Expressiveness of matchgates.
- Holographic Algorithms
- Holographic algorithms by Fibonacci gates
- Holographic algorithms: from art to science
- Holographic Algorithms: The Power of Dimensionality Resolved
- scientific article; zbMATH DE number 973924 (Why is no real title available?)
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- Nonintersecting paths, pfaffians, and plane partitions
- NP is as easy as detecting unique solutions
- On Symmetric Signatures in Holographic Algorithms
- On the computational complexity of the Jones and Tutte polynomials
- Pfaffian graphs, \(T\)-joins and crossing numbers
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Quantum computers that can be simulated classically in polynomial time
- Some Results on Matchgates and Holographic Algorithms
- Theory and Applications of Models of Computation
- Valiant's holant theorem and matchgate tensors
Cited in
(16)- On blockwise symmetric matchgate signatures and higher domain \#CSP
- Holographic algorithms by Fibonacci gates
- FKT is not universal -- a planar holant dichotomy for symmetric constraints
- Counting degree-constrained subgraphs and orientations
- A finite-tame-wild trichotomy theorem for tensor diagrams
- Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
- Holographic Algorithms
- Holographic algorithms: from art to science
- Some Results on Matchgates and Holographic Algorithms
- Generalized counting constraint satisfaction problems with determinantal circuits
- Computing the Tutte polynomial of lattice path matroids using determinantal circuits
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- \(P\) versus \(NP\) and geometry
- Holographic algorithms: from art to science
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
This page was built for publication: Holographic algorithms without matchgates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1931767)
