Spin glass and computational complexity


Report summary:

 Physics traditionally focuses on matter and various entities composed of matter. Data is not material, but it contains information and has a very rich internal structure. Computational complexity has become an important research object of statistical physics. Spin glass theory plays a very important role in understanding disordered spin interaction systems. In recent years, the theoretical framework also has many enlightening applications in constraint satisfaction, combinatorial optimization, statistical inference, neural networks and so on. I will briefly review the core physical ideas of spin glass theory, introduce replica method, cavity theory and belief propagation message passing algorithm, and discuss the relationship with large deviation theory.

Personal profile:

 Haijun Zhou, researcher of the Institute of theoretical physics, Chinese Academy of Sciences, executive deputy director of the frontier Key Laboratory of theoretical physics, Chinese Academy of Sciences, concurrently director of Minjiang Cooperation Center for theoretical physics, vice president of the school of Physical Sciences, University of Chinese Academy of Sciences, has been selected into the hundred talents program of Chinese Academy of Sciences and supported by the National Outstanding Youth Fund. He graduated from the Department of physics of Nankai University in 1995, obtained the doctor of Science degree of Chinese Academy of Sciences in 2000, engaged in post doctoral research at Max Planck colloid and interface Institute in Germany funded by Humboldt Foundation in 2000, joined the Institute of theoretical physics of Chinese Academy of Sciences in 2005, and won the 11th National Youth Science and Technology Award in 2010. The research field is statistical physics, especially focusing on the spin glass mean field theory and its application in interdisciplinary fields. Through theoretical derivation and computer simulation, the phase transition phenomenon in stochastic combinatorial optimization problem, random search algorithm, information transfer algorithm based on statistical physics theory, distributed learning mechanism in neural network and so on are studied. We also pay attention to the structural phase transition and entropy elasticity of single molecule biopolymers. He is now a member of the editorial board of Journal of statistical mechanics, scientific reports, science China: mechanics, physics and astronomy, communications in theoretical physics, Journal of Physics: complexity.