A complete dichotomy rises from the capture of vanishing signatures

DOI10.1145/2488608.2488687zbMath1293.68162OpenAlexW2054043146MaRDI QIDQ5495834

Tyson Williams, Jin-Yi Cai, Heng Guo

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2488608.2488687

zbMATH Keywords

computational complexitydichotomycounting complexityHolant problems\#CSPHolant*vanishing type Fibonacci gates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (18)

Zero-freeness and approximation of real Boolean Holant problems ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Graph parameters from symplectic group invariants ⋮ Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits ⋮ A finite-tame-wild trichotomy theorem for tensor diagrams ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ Complexity classification of the six-vertex model ⋮ On the Complexity of Holant Problems ⋮ A collapse theorem for holographic algorithms with matchgates on domain size at most 4 ⋮ Holographic algorithms on bases of rank 2 ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Unnamed Item ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ A dichotomy for real weighted Holant problems

This page was built for publication: A complete dichotomy rises from the capture of vanishing signatures