Valiant's holant theorem and matchgate tensors
From MaRDI portal
Publication:2382280
DOI10.1016/j.tcs.2007.05.015zbMath1124.68113OpenAlexW4213390282MaRDI QIDQ2382280
Publication date: 28 September 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.015
signaturesperfect matchingsholographic algorithmsmatchgridGrassmann-Plücker identitiesmatchgatesholantcovariant and contravariant tensorsmatchcircuit
Related Items
The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, The Complexity of Boolean Holant Problems with Nonnegative Weights, \(P\) versus \(NP\) and geometry, Holographic reduction, interpolation and hardness, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, Holographic algorithms by Fibonacci gates, Holographic algorithms without matchgates, Holographic algorithms: from art to science, Holographic algorithms on domains of general size, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Unnamed Item, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
Cites Work
- Unnamed Item
- Unnamed Item
- On the theory of matchgate computations
- Negation can be exponentially powerful
- The gap between monotone and non-monotone circuit complexity is exponential
- Expressiveness of matchgates.
- Gaussian elimination is not optimal
- The statistics of dimers on a lattice
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- On Symmetric Signatures in Holographic Algorithms
- Some Results on Matchgates and Holographic Algorithms
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Tensor Geometry
- Dimer problem in statistical mechanics-an exact result
- Holographic Algorithms: The Power of Dimensionality Resolved
- Automata, Languages and Programming
- Computing and Combinatorics
