Conference item icon

Conference item

Approximation via correlation decay when strong spatial mixing fails

Abstract:

Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of anti-ferromagnetic two-spin models.

Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means that one uses worst-case analysis of the recursive procedure that creates the sub-instances. In this...

Expand abstract
Publication status:
Accepted
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
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik Publisher's website
Host title:
43rd International Colloquium on Automata, Languages and Computation (ICALP2016)
Publication date:
2016-01-01
Acceptance date:
2016-04-14
ISSN:
1868-8969
Source identifiers:
619034
Keywords:
Pubs id:
pubs:619034
UUID:
uuid:d9ccf75b-0f46-4700-a1d0-f1b9e1f667ce
Local pid:
pubs:619034
Deposit date:
2016-05-02

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