FKT is not universal -- a planar holant dichotomy for symmetric constraints
From MaRDI portal
Publication:2075391
DOI10.1007/s00224-021-10032-1OpenAlexW3128901778MaRDI QIDQ2075391
Jin-Yi Cai, Tyson Williams, Heng Guo, Zhiguo Fu
Publication date: 14 February 2022
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-021-10032-1
Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Equilibrium statistical mechanics (82Bxx)
Related Items (5)
Holographic algorithms on domains of general size ⋮ A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory ⋮ Complexity classification of the eight-vertex model ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Bipartite 3-regular counting problems with mixed signs
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
- Characterizing partition functions of the vertex model
- Holographic algorithms: from art to science
- Spin systems on \(k\)-regular graphs with complex edge functions
- Characterizing partition functions of the spin model by rank growth
- On the theory of matchgate computations
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
- On symmetric signatures in holographic algorithms
- Some observations on holographic algorithms
- Holographic algorithms beyond matchgates
- Expressiveness of matchgates.
- Holographic algorithms without matchgates
- The complexity of planar Boolean \#CSP with complex weights
- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- A Complete Dichotomy Rises from the Capture of Vanishing Signatures
- The statistics of dimers on a lattice
- Computational Complexity of Holant Problems
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Holographic Algorithms
- On Tractable Exponential Sums
- Some Results on Matchgates and Holographic Algorithms
- Tensor Geometry
- The Complexity of Boolean Holant Problems with Nonnegative Weights
- Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
- Beitrag zur Theorie des Ferromagnetismus
- A New Holant Dichotomy Inspired by Quantum Computation
- Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
- Dimer problem in statistical mechanics-an exact result
- The Computational Complexity of Tutte Invariants for Planar Graphs
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- The Spontaneous Magnetization of a Two-Dimensional Ising Model
- Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
- Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
- Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
- The Complexity of Symmetric Boolean Parity Holant Problems
This page was built for publication: FKT is not universal -- a planar holant dichotomy for symmetric constraints
