1306.3978 (Mihailo Stojnic)

Asymmetric Little model and its ground state energies    [PDF]

Mihailo Stojnic

In this paper we look at a class of random optimization problems that arise in the forms typically known in statistical physics as Little models. In \cite{BruParRit92} the Little models were studied by means of the well known tool from the statistical physics called the replica theory. A careful consideration produced a physically sound conclusion that the behavior of almost all important features of the Little models essentially resembles the behavior of the corresponding ones of appropriately scaled Sherrington-Kirkpatrick (SK) model. In this paper we revisit the Little models and consider their ground state energies as one of their main features. We then rigorously show that they indeed can be lower-bounded by the corresponding ones related to the SK model. We also provide a mathematically rigorous way to show that the replica symmetric estimate of the ground state energy is in fact a rigorous upper-bound of the ground state energy. Moreover, we then recall on a set of powerful mechanisms we recently designed for a study of the Hopfield models in \cite{StojnicHopBnds10,StojnicMoreSophHopBnds10} and show how one can utilize them to substantially lower the upper-bound that the replica symmetry theory provides.

View original: http://arxiv.org/abs/1306.3978