# Summer Graduate School

Parent Program: |
-- |
---|---|

Location: |
Centre de Recherches Mathématicques, Montréal, Canada |

**Due to the COVID-19 pandemic, this summer school will likely be held online.**

Probability theory, statistics as well as mathematical physics have increasingly been used in computer science. The goal of this school is to provide a unique opportunity for graduate students and young researchers to developed multi-disciplinary skills in a rapidly evolving area of mathematics.

The topics would include spin glasses, constraint satisfiability, randomized algorithms, Monte-Carlo Markov chains and high-dimensional statistics, sparse and random graphs, computational complexity, estimation and approximation algorithms. Those topics will fall into two main categories, on the one hand problems related to spin glasses and on the other hand random algorithms.

The part of the summer school dedicated to spin glasses will be split into three parts: an introductory course about traditional spin glasses followed by two more advanced courses where spin glasses meet computer science in addition to a talk on dynamics of spin glasses. The part of the summer school on random algorithms will consist of an introductory course on phase transitions in large random structures, followed by advanced courses on theoretical bounds for computational complexity in reconstruction and inference, and on understanding rare events in random graphs and models of statistical mechanics.

The two introductory courses on spin glasses and on random algorithms will be accompanied by three exercises sessions of one hour. A one hour exercises session will follow each of the three sessions of a course for both the introductory course on spin glasses and the introductory course on random algorithms. Exercises sessions will be led by an assistant, but will primarily focus on participation of the students.

For more infomartion, please see this LINK.

**Suggested Prerequisites**

The students are expected to have previously learned the theory of random variables, law of large numbers, central limit theorem, discrete time Markov chains. The two main references for this content includes: *A first course in probability* by Ross (Chapters 1-8) and *Markov chains* by Norris (or http://www.statslab.cam.ac.uk/ ~rrw1/markov/M.pdf Chapter 1-10).

We also recommend *Probability and Random processes* by Grimmett and Stirzaker. This excellent book will cover all the important material (Chapter 1-6) in Ross and Norris. It will also provide a deeper introduction to two central tools: Gaussian vectors (Chapter 4.9) and large deviations (Chapter 5.11). These topics are also covered in *Probability: theory and examples* by Durrett.

We also recommend https://www.probabilitycourse.com/ by Pishro-Nik which contains an introduction to the terminology used in statistics (Chapter 8-9). Chapters 1-7 can also be used as an introduction to probability theory.

The students should also have basic notions on Markov Chain Monte Carlo and Markov chain mixing. For this, we recommend the first five chapters of *Markov chains and mixing times* by Levin, Peres and Wilmer available at https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf.

Finally, the students who are less familiar with physics terminology (such as phase transitions) or information theory (such as entropy) should look at *Information physics and computation* by Mezard and Montanari. We want to emphasize that this book may heavily intersect with the course given by Andrea Montanari.

For **eligibility** and **how to apply**, see the **Summer Graduate Schools homepage**

**Due to the small number of students supported by MSRI, only one student per institution will be funded by MSRI. This school may require an additional application with SMS directly.**

**Keywords and Mathematics Subject Classification (MSC)**

**Tags/Keywords**

spin glasses

constraint satisfiability

algorithms and information theory

high-dimensional statistics

statistical network analysis

community detection

**Primary Mathematics Subject Classification**

60J10 - Markov chains (discrete-time Markov processes on discrete state spaces)

68Rxx - Discrete mathematics in relation to computer science

**Secondary Mathematics Subject Classification**No Secondary AMS MSC