In the last decades the tl1eory of spin glasses has been developed within the framework of statistical physics. The obtained results showed to be novel not only from the physical point of vie\l\'1 but they have brought also new mathematical techniques and algorithmic approaches. Indeed, the problem of finding ground state of a spin glass is (in general) NP-complete. The methods that were found brought new ideas to the field of Combinatorial Optimization, and on the other side, the similar methods of Combinatorial Optimization, were applied in physical systems. As it happened with the Monte Carlo sampling and the Simulated Annealing, also the novel Cavity Method lead to algorithms that are open to wide use in various fields of research The Cavity Method shows to be equivalent to Bethe Approximation in its most symmetric version, and the derived algorithm is equivalent to the Belief Propagation, an inference method used widely for example in the field of Pattern Recognition. The Cavity Method in a less symmetric situation, when one has to consider correctly the clustering of the configuration space, lead to a novel messagepassing algorithm-the Survey Propagation. The class of Message-Passing algorithms, among which both the Belief Propagation and the Survey Propagation belong, has found its application as Inference Algorithms in many engineering fields. Among others let us :mention the Low-Density Parity-Check Codes, that are widely used as ErrorCorrecting Codes for communication over noisy cha1mels. In the first part of this work we have compared efficiency of the Survey Propagation Algorithm and of standard heuristic algorithms in the case of the random-MAX-K-SAT problem. The results showed that the algorithms perform similarly in the regions where the clustering of configuration space does not appeai~ but that the Survey Propagation finds much better solutions to the optimization problem in the critical region where one has to consider existence of many ergodic components explicitly. The second part of the thesis targets the problem of protein structure and flexibility. In many proteins the mobility of certain regions and rigidity of other regions of their structure is crucial for their function or interaction with other cellular elements. Our simple model tries to point out the flexible regions from the knowledge of native 3D-structure of the protein. The problem is mapped to a spin glass model which is successfully solved by the Believe Propagation algorithm.
|Titolo:||Statistical Physics and Message Passing Algorithms. Two Case Studies: MAX-K-SAT Problem and Protein Flexibility|
|Relatore/i esterni:||Zecchina, Riccardo|
|Data di pubblicazione:||20-gen-2006|
|Appare nelle tipologie:||8.1 PhD thesis|