FKT is not universal -- a planar holant dichotomy for symmetric constraints
type: Item
instance of: scholarly article
title: FKT is not universal -- a planar holant dichotomy for symmetric constraints
author: Jin-Yi Cai
author: Zhiguo Fu
author: Heng Guo
author: Tyson Williams
published in: Theory of Computing Systems
publication date: 2022-02-14T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
Mathematics Subject Classification ID: 82Bxx
Mathematics Subject Classification ID: 68Rxx
zbMATH DE Number: 7473209
zbMATH Keywords: computational complexity
zbMATH Keywords: counting
zbMATH Keywords: holographic algorithms
MaRDI profile type: Publication
full work available at URL: s00224-021-10032-1
OpenAlex ID: W3128901778
cites work: A New Holant Dichotomy Inspired by Quantum Computation
cites work: Q5002678
cites work: Q3324796
cites work: On Tractable Exponential Sums
cites work: Some Results on Matchgates and Holographic Algorithms
cites work: On the theory of matchgate computations
cites work: Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
cites work: Q3191606
cites work: A complete dichotomy rises from the capture of vanishing signatures
cites work: Holographic algorithms beyond matchgates
cites work: Spin systems on \(k\)-regular graphs with complex edge functions
cites work: Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
cites work: On symmetric signatures in holographic algorithms
cites work: Holographic algorithms: from art to science
cites work: Computational Complexity of Holant Problems
cites work: The complexity of complex weighted Boolean \#CSP
cites work: Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
cites work: Q4608007
cites work: Dichotomy for Holant\(^\ast\) problems on the Boolean domain
cites work: Tensor Geometry
cites work: Characterizing partition functions of the vertex model
cites work: Reflection positivity, rank connectivity, and homomorphism of graphs
cites work: The complexity of symmetric Boolean parity Holant problems
cites work: The complexity of planar Boolean \#CSP with complex weights
cites work: A dichotomy for real weighted Holant problems
cites work: Beitrag zur Theorie des Ferromagnetismus
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: Holographic algorithms without matchgates
cites work: Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
cites work: The Complexity of Boolean Holant Problems with Nonnegative Weights
cites work: Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
cites work: Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
cites work: Characterizing partition functions of the spin model by rank growth
cites work: Dimer problem in statistical mechanics-an exact result
cites work: Expressiveness of matchgates.
cites work: Quantum Circuits That Can Be Simulated Classically in Polynomial Time
cites work: Holographic Algorithms
cites work: Some observations on holographic algorithms
cites work: The Computational Complexity of Tutte Invariants for Planar Graphs
cites work: Q3140234
cites work: The Spontaneous Magnetization of a Two-Dimensional Ising Model
cites work: Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
DOI: 10.1007/S00224-021-10032-1
description: scientific article; zbMATH DE number 7473209