NDLI: Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant

Content Provider	IEEE Xplore Digital Library
Author	Sinclair, A. Srivastava, P. Yitong Yin
Copyright Year	2013
Description	Author affiliation: Comput. Sci. Div., UC Berkeley, Berkeley, CA, USA (Sinclair, A.; Srivastava, P.) \|\| State Key Lab. for Novel Software Technol., Nanjing Univ., Nanjing, China (Yitong Yin)
Abstract	The hard core model in statistical physics is a probability distribution on independent sets in a graph in which the weight of any independent set I is proportional to $λ^{\|I\|},$ where λ > 0 is the vertex activity. We show that there is an intimate connection between the connective constant of a graph and the phenomenon of strong spatial mixing (decay of correlations) for the hard core model; specifically, we prove that the hard core model with vertex activity λ <; $λ_{c}(Δ+1)$ exhibits strong spatial mixing on any graph of connective constant Δ, irrespective of its maximum degree, and hence derive an FPTAS for the partition function of the hard core model on such graphs. Here $λ_{c}(d)$ ··= $d^{d}/(d-1)^{d+1}$ is the critical activity for the uniqueness of the Gibbs measure of the hard core model on the infinite d-ary tree. As an application, we show that the partition function can be efficiently approximated with high probability on graphs drawn from the random graph model G (n, d/n) for all λ <; e/d, even though the maximum degree of such graphs is unbounded with high probability. We also improve upon Weitz's bounds for strong spatial mixing on bounded degree graphs [30] by providing a computationally simple method which uses known estimates of the connective constant of a lattice to obtain bounds on the vertex activities λ for which the hard core model on the lattice exhibits strong spatial mixing. Using this framework, we improve upon these bounds for several lattices including the Cartesian lattice in dimensions 3 and higher. Our techniques also allow us to relate the threshold for the uniqueness of the Gibbs measure on a general tree to its branching factor [15].
Starting Page	300
Ending Page	309
File Size	286825
Page Count	10
File Format	PDF
ISBN	9780769551357
ISSN	02725428
DOI	10.1109/FOCS.2013.40
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-26
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Lattices Correlation Approximation methods Approximation algorithms Partitioning algorithms Physics Boundary conditions connective constant Decay of correlations approximate counting phase transitions
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Spatial mixing and approximation algorithms for graphs with bounded connective constant

Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Approximate counting via correlation decay on planar graphs.

Spatial mixing and approximate counting for Potts model on graphs with bounded average degree

Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs

Counting and Correlation Decay in Spin Systems

Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets

Computer-Assisted Verification Method for Invariant Densities and Rates of Decay of Correlations

Approximate Counting via Correlation Decay on Planar Graphs

Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant

Similar Documents

Spatial mixing and approximation algorithms for graphs with bounded connective constant

Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Approximate counting via correlation decay on planar graphs.

Spatial mixing and approximate counting for Potts model on graphs with bounded average degree

Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs

Counting and Correlation Decay in Spin Systems

Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets

Computer-Assisted Verification Method for Invariant Densities and Rates of Decay of Correlations

Approximate Counting via Correlation Decay on Planar Graphs

Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant