Por favor, use este identificador para citar o enlazar este ítem: https://hdl.handle.net/10495/33407
Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.contributor.authorRestrepo López, Ricardo-
dc.contributor.authorShin, Jinwoo-
dc.contributor.authorTetali, Prasad-
dc.contributor.authorVigoda, Eric-
dc.contributor.authorYang, Linji-
dc.description.abstractABSTRACT: The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ |I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree ∆ ≥ 3, is a well known computationally challenging problem. More concretely, let λc(T∆) denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite ∆-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified λc(T∆) as a threshold where the hardness of estimating the above partition function undergoes a computational transition. We focus on the well-studied particular case of the square lattice Z 2, and provide a new lower bound for the uniqueness threshold, in particular taking it well above λc(T4). Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to Z 2 we prove that strong spatial mixing holds for all λ < 2.3882, improving upon the work of Weitz that held for λ < 27/16 = 1.6875. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution.spa
dc.publisherUniversidad de Antioquiaspa
dc.publisherGeorgia Institute of Technologyspa
dc.titleImproved Mixing Condition on the Grid for Counting and Sampling Independent Setsspa
dc.publisher.groupAnálisis Numérico y Financiero: Matemáticas aplicadas para la industriaspa
dc.publisher.placeAtlanta, Estados Unidosspa
dc.type.localDocumento de trabajospa
dc.subject.lembGas reticular-
dc.subject.lembLattice gas-
dc.subject.lembAnálisis numérico-
dc.subject.lembNumerical analysis-
dc.subject.lembTransformaciones de fase (física estadística)-
dc.subject.lembFase transformations (statistical physics)-
dc.subject.proposalMedidas de Gibbsspa
dc.subject.proposalGibbs measuresspa
dc.subject.proposalDinámica de Glauberspa
dc.subject.proposalGlauber dynamicsspa
Aparece en las colecciones: Documentos de Trabajo en Ciencias Exactas y Naturales

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
RestrepoRicardo_2011_ImprovedMixingCondition.pdfDocumento de trabajo516.49 kBAdobe PDFVisualizar/Abrir

Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons