Show simple item record

dc.contributor.authorYang, Linjien_US
dc.date.accessioned2013-06-15T02:43:19Z
dc.date.available2013-06-15T02:43:19Z
dc.date.issued2013-04-02en_US
dc.identifier.urihttp://hdl.handle.net/1853/47593
dc.description.abstractSpin systems are powerful mathematical models widely used and studied in Statistical Physics and Computer Science. This thesis focuses the study of spin systems on colorings and weighted independent sets (the hard-core model). In many spin systems, there exist phase transition phenomena: there is a threshold value of a parameter such that when the parameter is on one side of the threshold, the system exhibits the so-called spatial decay of correlation, i.e., the influence from a set of vertices to another set of vertices diminishes as the distance between the two sets grows; when the parameter is on the other side, long range correlations persist. The uniqueness problem and the reconstruction problem are two major threshold problems that are concerned with the decay of correlations in the Gibbs measure from different perspectives. In Computer Science, the study of spin systems mainly focused on finding an efficient algorithm that samples the configurations from a distribution that is very close to the Gibbs measure. Glauber dynamics is a typical Markov chain algorithm for performing sampling. In many systems, the convergence time of the Glauber dynamics also exhibits a threshold behavior: the speed of convergence experiences a dramatic change around the threshold of the parameter. The first two parts of this thesis focus on making connections between the phase transition of the convergence time of the dynamics and the phase transition of the reconstruction phenomenon in both colorings and the hard-core model on regular trees. A relatively sharp threshold is established for the change of the convergence time, which coincides with the reconstruction threshold. A general technique of upper bounding the conductance of the dynamics via analyzing the sensitivity of the reconstruction algorithm is proposed and proven to be very effective for lower bounding the convergence time of the dynamics. The third part of the thesis provides an innovative analytical method for establishing a strong version of the decay of correlation of the Gibbs distributions for many two spin systems on various classes of graphs. In particular, the method is applied to the hard-core model on the square lattice, a very important graph that is of great interest in both Statistical Physics and Computer Science. As a result, we significantly improve the lower bound of the uniqueness threshold on the square lattice and extend the range of parameter where the Glauber dynamics is rapidly mixing.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectSpin systemsen_US
dc.subjectGlauber dynamicsen_US
dc.subjectMarkov chainen_US
dc.subjectMixing timeen_US
dc.subjectUniquenessen_US
dc.subjectPhase transitionsen_US
dc.subject.lcshMarkov processes
dc.subject.lcshStochastic processes
dc.subject.lcshAlgorithms
dc.titlePhase transitions in spin systems: uniqueness, reconstruction and mixing timeen_US
dc.typeDissertationen_US
dc.description.degreePhDen_US
dc.contributor.departmentComputer Scienceen_US
dc.description.advisorCommittee Chair: Vigoda, Eric; Committee Member: Randall, Dana; Committee Member: Stefankovic, Daniel; Committee Member: Tetali, Prasad; Committee Member: Vempala, Santoshen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record