Super Global Course Special Lectures by Prof. Amir Dembo (Kyoto / Stanford) will take place as follows:

Course Title

Super Global Course Special Lectures 2

Date & Time

October 28 - November 18, 2016
Fri, Oct 28, 12:30-14:30
Tue, Nov 1, 13:00-15:00
Tue, Nov 8, 14:45-16:45
Fri, Nov 11, 14:30-16:30
Fri, Nov 18, 14:30-16:30

Venue

127 Conference room, Faculty of Science Bldg. #3, Kyoto University

Title

Statistical physics on sparse random graphs: A mathematical perspective

Abstract

Theoretical models of disordered materials yield precise predictions about the typical complexity of certain combinatorial optimization problems. The underlying common structure is that of many discrete variables, whose interaction is represented by a random 'tree like' sparse graph. I will survey recent progress in proving such predictions, the related insights gained from it, and certain interesting connections with spin-glass models, random matrices and extremal graphs.
Below is the plan of lectures.

Lecture 1:

Statistical Physics and Computation: Boltzmann-Gibbs distributions, factor models and Constraint Satisfaction Problems. Average complexity, ground states and sparse random graph ensembles. Locally tree-like graphs, Bethe-Peierls prediction and Belief Propagation equations.

Lecture 2:

Extremal cuts: From Sparse random graphs to spin-glasses.

Lecture 3:

The ferromagnetic Potts (and Ising) model: Proving replica-symmetric free energy prediction by interpolation and graph decimation.

Lecture 4:

Non-linear large deviations in counting (sparse) graph homeomorphisms and k-arithmetic progressions.

Lecture 5:

Gibbs measures, the set of near-optimal solutions for CSP-s and justifying the one Replica-Symmetry-Breaking prediction.

Language

English

Note

This series of lectures will be video-recorded and made available online.
Please note that anyone in the front rows of the room can be captured by a video camera.