Journal article icon

Journal article

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Abstract:

One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite Δ-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on k-uniform hypergra...

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

Actions


Access Document


Publisher copy:
10.1016/j.ic.2016.07.003

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Elsevier Publisher's website
Journal:
Information and Computation Journal website
Volume:
251
Pages:
36-66
Publication date:
2016-11-05
Acceptance date:
2016-06-20
DOI:
ISSN:
1090-2651
URN:
uuid:116ad3d0-b25c-4ead-a3df-c05c4af1b1fc
Source identifiers:
633069
Local pid:
pubs:633069

Terms of use


Metrics


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