Holographic algorithms beyond matchgates

DOI10.1016/j.ic.2018.01.002zbMath1390.68338arXiv1307.7430OpenAlexW3021422422MaRDI QIDQ1706145

Tyson Williams, Heng Guo, Jin-Yi Cai

Publication date: 21 March 2018

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.7430

zbMATH Keywords

counting complexityholographic algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Holographic algorithms beyond matchgates ⋮ Clifford gates in the Holant framework ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• The complexity of complex weighted Boolean \#CSP
• Holographic algorithms: from art to science
• Signature theory in holographic algorithms
• Spin systems on \(k\)-regular graphs with complex edge functions
• The complexity of weighted Boolean \#CSP with mixed signs
• On the theory of matchgate computations
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On the complexity of H-coloring
• Holographic algorithms beyond matchgates
• Expressiveness of matchgates.
• Holographic reduction, interpolation and hardness
• Holographic algorithms by Fibonacci gates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of planar Boolean \#CSP with complex weights
• The complexity of partition functions
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• Gadgets and anti-gadgets leading to a complexity dichotomy
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• The statistics of dimers on a lattice
• Computational Complexity of Holant Problems
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• The Complexity of Weighted Boolean #CSP
• Tensor Geometry
• Complexity of Counting CSP with Complex Weights
• Dimer problem in statistical mechanics-an exact result
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• Affine projections of polynomials
• Operations with structures
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• Dichotomy for Holant Problems with a Function on Domain Size 3
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem

This page was built for publication: Holographic algorithms beyond matchgates