Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
From MaRDI portal
Publication:898252
DOI10.1016/j.jsc.2015.06.008zbMath1346.68295arXiv1311.4066OpenAlexW2171050449MaRDI QIDQ898252
Publication date: 8 December 2015
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.4066
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Combinatorics in computer science (68R05) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)
Related Items (2)
A finite-tame-wild trichotomy theorem for tensor diagrams ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints
Uses Software
Cites Work
- Unnamed Item
- The complexity of complex weighted Boolean \#CSP
- Generalized counting constraint satisfaction problems with determinantal circuits
- Nowhere-zero flow polynomials
- The complexity of weighted Boolean \#CSP with mixed signs
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Colorings and orientations of graphs
- Stable sets and polynomials
- Holographic algorithms without matchgates
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- The complexity of planar Boolean \#CSP with complex weights
- Valiant's holant theorem and matchgate tensors
- The complexity of partition functions
- Gadgets and anti-gadgets leading to a complexity dichotomy
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- On the complexity of #CSP
- Computational Complexity of Holant Problems
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Holographic Algorithms
- Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
- The Complexity of Weighted Boolean #CSP
- Combinatorial Nullstellensatz
- Holant problems and counting CSP
- The complexity of the counting constraint satisfaction problem
- Complexity of counting CSP with complex weights
- A Simple Algorithm for Mal'tsev Constraints
- A complete dichotomy rises from the capture of vanishing signatures
- Dichotomy for Holant Problems with a Function on Domain Size 3
This page was built for publication: Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
