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


Files:

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
More from this funder
Name:
European Research Council
Grant:
334828
Publisher:
Elsevier
Journal:
Information and Computation More from this journal
Volume:
251
Pages:
36-66
Publication date:
2016-11-01
Acceptance date:
2016-06-20
ISSN:
1090-2651
Keywords:
Pubs id:
pubs:633069
UUID:
uuid:6a494fc4-a05d-4257-a039-bdcbcbe452e5
Local pid:
info:fedora/pubs:633069
Source identifiers:
633069
Deposit date:
2016-07-11

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