Journal article icon

Journal article

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

Abstract:

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 strictly increasing unary function and any permissive strictly decreasing unary function, and requiring only those to be in F. The resulting classification is employed to characterise the complexit...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jcss.2019.12.003

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
ORCID:
0000-0002-0263-159X
Publisher:
Elsevier Publisher's website
Journal:
Journal of Computer and System Sciences Journal website
Volume:
109
Pages:
95-125
Publication date:
2019-12-27
Acceptance date:
2019-12-15
DOI:
EISSN:
1090-2724
ISSN:
0022-0000
Source identifiers:
1077893
Language:
English
Keywords:
Pubs id:
pubs:1077893
UUID:
uuid:c63dffdf-b353-453a-850f-bd635baf2827
Local pid:
pubs:1077893
Deposit date:
2019-12-15

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP