Bounded degree nonnegative counting CSP
From MaRDI portal
complexity dichotomycomputational counting complexityconstraint satisfaction problemscounting CSPsgraph homomorphismsnonnegative counting CSP
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)
Cites work
- A complexity classification of spin systems with an external field
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- A new look at survey propagation and its generalizations
- An effective dichotomy for the counting constraint satisfaction problem
- Approximate counting via correlation decay in spin systems
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Belief propagation for continuous state spaces: stochastic message-passing with quantitative guarantees
- Combinatorics and complexity of partition functions
- Complexity classifications of Boolean constraint satisfaction problems
- Complexity Dichotomies for Counting Problems
- Complexity of counting CSP with complex weights
- Complexity of generalized satisfiability counting problems
- Conditional Hardness for Approximate Coloring
- Correlation decay up to uniqueness in spin systems
- Counting graph homomorphisms
- Counting independent sets up to the tree threshold
- Dichotomy for graph homomorphisms with complex values on bounded degree graphs
- Graph homomorphisms and phase transitions
- Holographic reduction: a domain changed application and its partial converse theorems
- How to Round Any CSP
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- Large networks and graph limits
- MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
- Non-uniqueness of measures of maximal entropy for subshifts of finite type
- On Counting Homomorphisms to Directed Acyclic Graphs
- On Counting Independent Sets in Sparse Graphs
- Operations with structures
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Some optimal inapproximability results
- Spatial mixing and approximation algorithms for graphs with bounded connective constant
- Spin Glass approach to the feedback vertex set problem
- Survey propagation: An algorithm for satisfiability
- The complexity of Boolean Holant problems with nonnegative weights
- The complexity of complex weighted Boolean \#CSP
- The complexity of partition functions
- The Complexity of the Counting Constraint Satisfaction Problem
- The complexity of weighted and unweighted \(\#\)CSP
- The computational hardness of counting in two-spin models on d-regular graphs
- Towards a dichotomy theorem for the counting constraint satisfaction problem
This page was built for publication: Bounded degree nonnegative counting CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7022392)
