dc.contributor |
Centre de Recerca Matemàtica |
dc.contributor.author |
Sinclair, Alistair |
dc.contributor.author |
Srivastava, Piyush |
dc.contributor.author |
Thurley, Marc |
dc.date.accessioned |
2011-10-26T07:26:41Z |
dc.date.available |
2011-10-26T07:26:41Z |
dc.date.created |
2011 |
dc.date.issued |
2011 |
dc.identifier.uri |
http://hdl.handle.net/2072/171420 |
dc.format.extent |
20 |
dc.format.extent |
321418 bytes |
dc.format.mimetype |
application/pdf |
dc.language.iso |
eng |
dc.publisher |
Centre de Recerca Matemàtica |
dc.relation.ispartofseries |
Prepublicacions del Centre de Recerca Matemàtica;1038 |
dc.rights |
Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús (http://creativecommons.org/licenses/by-nc-nd/2.5/es/) |
dc.subject.other |
Aproximació, Teoria de l' |
dc.subject.other |
Algorismes |
dc.title |
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs |
dc.type |
info:eu-repo/semantics/preprint |
dc.subject.udc |
517 - Anàlisi |
dc.description.abstract |
In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree.
ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if
here is an FPRAS for the hard-core partition function on graphs of maximum
egree d for activities larger than the critical activity on the innite d-regular
ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing.
his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems. |