Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin

We analyse the complexity of approximate counting constraint satisfactions problems #CSP(F), where F is a set of nonnegative rational-valued functions of Boolean variables. A complete classification is known if F contains arbitrary unary functions. We strengthen this result by fixing any permissive...

Bibliografske podrobnosti
Main Authors:	Backens, M, Bulatov, A, Goldberg, LA, McQuillan, C, Živný, S
Format:	Journal article
Jezik:	English
Izdano:	Elsevier 2019

Podobne knjige/članki

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
od: Goldberg, L, et al.
Izdano: (2016)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, et al.
Izdano: (2017)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, et al.
Izdano: (2017)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, et al.
Izdano: (2018)

The complexity of conservative valued CSPs
od: Kolmogorov, V, et al.
Izdano: (2011)

The complexity of conservative valued CSPs
od: Kolmogorov, V, et al.
Izdano: (2013)

The complexity of conservative valued CSPs
od: Kolmogorov, V, et al.
Izdano: (2012)

Pliability and approximating max-CSPs
od: Romero, M, et al.
Izdano: (2023)

The complexity of conservative finite-valued CSPs
od: Kolmogorov, V, et al.
Izdano: (2010)

Approximate counting CSP seen from the other side
od: Bulatov, A, et al.
Izdano: (2020)

Approximate counting CSP seen from the other side
od: Bulatov, A, et al.
Izdano: (2019)

The complexity of approximately counting retractions
od: Focke, J, et al.
Izdano: (2020)

Holant clones and the approximability of conservative holant problems
od: Backens, M, et al.
Izdano: (2020)

The complexity of approximately counting retractions
od: Focke, J, et al.
Izdano: (2019)

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
od: Galanis, A, et al.
Izdano: (2017)

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
od: Galanis, A, et al.
Izdano: (2020)

Sparsification of binary CSPs
od: Butti, S, et al.
Izdano: (2020)

Sparsification of Binary CSPs
od: Butti, S, et al.
Izdano: (2019)

On planar valued CSPs
od: Fulla, P, et al.
Izdano: (2016)

Additive sparsification of CSPs
od: Pelleg, E, et al.
Izdano: (2021)

Additive sparsification of CSPs
od: Pelleg, E, et al.
Izdano: (2023)

On planar valued CSPs
od: Fulla, P, et al.
Izdano: (2017)

An approximation trichotomy for Boolean #CSP
od: Dyer, M, et al.
Izdano: (2010)

Counting list matrix partitions of graphs
od: Göbel, A, et al.
Izdano: (2013)

Counting list matrix partitions of graphs
od: Göbel, A, et al.
Izdano: (2015)

The complexity of approximately counting retractions to square-free graphs
od: Focke, J, et al.
Izdano: (2021)

The complexity of finite-valued CSPs
od: Thapper, J, et al.
Izdano: (2016)

The Complexity of Finite-Valued CSPs
od: Thapper, J, et al.
Izdano: (2013)

The complexity of finite-valued CSPs
od: Thapper, J, et al.
Izdano: (2013)

On Approximability of Satisfiable k-CSPs: II
od: Bhangale, Amey, et al.
Izdano: (2023)

On Approximability of Satisfiable k-CSPs: III
od: Bhangale, Amey, et al.
Izdano: (2023)

On approximability of satisfiable k -CSPs: I
od: Bhangale, Amey, et al.
Izdano: (2022)

Point-width and max-CSPs
od: Carbonnel, C, et al.
Izdano: (2019)

Point-width and Max-CSPs
od: Carbonnel, C, et al.
Izdano: (2020)

Approximately counting answers to conjunctive queries with disequalities and negations
od: Focke, J, et al.
Izdano: (2022)

Approximately counting answers to conjunctive queries with disequalities and negations
od: Focke, J, et al.
Izdano: (2024)

The Power of Linear Programming for Valued CSPs
od: Thapper, J, et al.
Izdano: (2012)

The power of linear programming for valued CSPs
od: Thapper, J, et al.
Izdano: (2015)

The power of linear programming for valued CSPs
od: Thapper, J, et al.
Izdano: (2012)

Sherali-Adams relaxations for valued CSPs
od: Thapper, J, et al.
Izdano: (2015)