The complexity of planar Boolean \#CSP with complex weights

DOI10.1016/j.jcss.2019.07.005zbMath1436.68135arXiv1212.2284OpenAlexW2967145908MaRDI QIDQ2009629

Tyson Williams, Heng Guo

Publication date: 29 November 2019

Published in: Journal of Computer and System Sciences, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsdichotomyconstraint satisfaction problemscounting complexity\#Pholographic algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items

On Planar Boolean CSP, On blockwise symmetric matchgate signatures and higher domain \#CSP, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, On planar valued CSPs, Holographic algorithms on domains of general size, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, A strengthening and an efficient implementation of Alon-Tarsi list coloring method, Holographic algorithms beyond matchgates, Counting Constraint Satisfaction Problems., A collapse theorem for holographic algorithms with matchgates on domain size at most 4, Holographic algorithms on bases of rank 2, The complexity of planar Boolean \#CSP with complex weights, 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
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• 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 symmetric signatures in holographic algorithms
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• Expressiveness of matchgates.
• Holographic reduction, interpolation and hardness
• Holographic algorithms by Fibonacci gates
• The complexity of planar Boolean \#CSP with complex weights
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• Gadgets and anti-gadgets leading to a complexity dichotomy
• The statistics of dimers on a lattice
• Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities
• Computational Complexity of Holant Problems
• Holant Problems for Regular Graphs with Complex Edge Functions
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• Tensor Geometry
• Beitrag zur Theorie des Ferromagnetismus
• Holant problems and counting CSP
• Dimer problem in statistical mechanics-an exact result
• Paths, Trees, and Flowers
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The Computational Complexity of Tutte Invariants for Planar Graphs
• A complete dichotomy rises from the capture of vanishing signatures
• 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
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem