Grant: Discovery Grants Program - Individual
University of Toronto
$20,000.00
Structure of the Gibbs distribution in spin glass models with applications
FY 2017-18
Summary
The main questions studied in this proposal originate from the models that were introduced by the physicists about forty years ago with the goal of understanding the unusual magnetic behavior of certain metal alloys, called spin glasses. The study of these models produced many new ideas that found unexpected applications beyond their original motivation. One of the most interesting applications was to the area of optimization problems. To give one example, let us consider a large group of people where any two are either friends or enemies, and let us divide them into two groups attempting to keep friends together and separate the enemies. This can not always be done perfectly, because if two of your friends are enemies then either you lose one of your friends or they will stay enemies inside your group; these are called frustrated triples. This problem of dividing the group in an optimal way is known to be very difficult to solve in general (imagine a situation with numerous frustrated triples), but there are many interesting questions one can ask about what happens in a typical situation. For example, one can ask how optimal solutions typically look like, or how other almost optimal solutions are related to the optimal ones. The physicists were very successful in applying the ideas developed in the study of spin glasses to various optimization problems arising in mathematics (traveling salesman problem, graph partitioning), computer science (random satisfiability of Boolean formulas) and biology (brain modeling), and their main contributions can be roughly divided into two categories. On the one hand, they have developed a very deep and sophisticated theoretical picture describing what happens in a typical situation in these optimization problems (where a typical situation is modeled by choosing the parameters of the problem randomly). On the other hand, having this picture in mind allowed them to come up with efficient algorithms for solving some of these problems in practice. The focus of this proposal is on the first category, namely, the physicists' theoretical picture in one family of models - the so called diluted spin glass models that include the random satisfiability models from computer science or a modification of the above problem of splitting a group of people into two groups in the case when each person interacts with only a small number of other people. The main goal of the proposal is to find a rigorous mathematical explanation for the picture proposed by the physicists in these models. In particular, the proposal attempts to prove a famous formula for the free energy and describe the structure of the Gibbs measure in these models. Just like the work of the physicists was based on the ideas developed in the context of the models of spin glasses, this proposal builds upon a significant progress achieved in recent years in the rigorous mathematical theory behind the original spin glass models.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-04637
Name nom
Panchenko, Dmitriy
Department département
Mathematics (St. George Campus) - Mathematics (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2015
Award amount
20000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
3006
Research subject group en
Statistics and probability
Research subject group fr
Statistique et probabilité
Research subject en
Probability theory
Research subject fr
Théorie de la probabilité
Partie
3
Nb partie
5
Application title
Structure of the Gibbs distribution in spin glass models with applications
Keyword
NSERC
Application summary
The main questions studied in this proposal originate from the models that were introduced by the physicists about forty years ago with the goal of understanding the unusual magnetic behavior of certain metal alloys, called spin glasses. The study of these models produced many new ideas that found unexpected applications beyond their original motivation. One of the most interesting applications was to the area of optimization problems. To give one example, let us consider a large group of people where any two are either friends or enemies, and let us divide them into two groups attempting to keep friends together and separate the enemies. This can not always be done perfectly, because if two of your friends are enemies then either you lose one of your friends or they will stay enemies inside your group; these are called frustrated triples. This problem of dividing the group in an optimal way is known to be very difficult to solve in general (imagine a situation with numerous frustrated triples), but there are many interesting questions one can ask about what happens in a typical situation. For example, one can ask how optimal solutions typically look like, or how other almost optimal solutions are related to the optimal ones. The physicists were very successful in applying the ideas developed in the study of spin glasses to various optimization problems arising in mathematics (traveling salesman problem, graph partitioning), computer science (random satisfiability of Boolean formulas) and biology (brain modeling), and their main contributions can be roughly divided into two categories. On the one hand, they have developed a very deep and sophisticated theoretical picture describing what happens in a typical situation in these optimization problems (where a typical situation is modeled by choosing the parameters of the problem randomly). On the other hand, having this picture in mind allowed them to come up with efficient algorithms for solving some of these problems in practice. The focus of this proposal is on the first category, namely, the physicists' theoretical picture in one family of models - the so called diluted spin glass models that include the random satisfiability models from computer science or a modification of the above problem of splitting a group of people into two groups in the case when each person interacts with only a small number of other people. The main goal of the proposal is to find a rigorous mathematical explanation for the picture proposed by the physicists in these models. In particular, the proposal attempts to prove a famous formula for the free energy and describe the structure of the Gibbs measure in these models. Just like the work of the physicists was based on the ideas developed in the context of the models of spin glasses, this proposal builds upon a significant progress achieved in recent years in the rigorous mathematical theory behind the original spin glass models.