Short course

Random combinatorial problems
Replica techniques and Algorithmic methods

Lectures will be in the Physics/Astronomy department which is now located in the new Biophysical Sciences (BPS) building on the campus of Michigan State Univ. 10th-15th May, 2002

Remi Monasson - Replica techniques
P. M. Duxbury - Algorithmic methods

Random combinatorial problems arise in a vast array of situations in physics, engineering, computer science, applied mathematics and combinatorics. In physics, the classic example is the Ising spin glass, while in combinatorial optimization the NP-complete class lies at the nexus of these problems. The replica method is making a significant impact on the analysis of these difficult random combinatorial problems. The first objective of this short course is to give an up to date account of the replica approach to hard random combinatorial problems, and to compare the replica results with numerical results. The second objective of this short course is to discuss algorithms which can find the true ground state of P and NP-complete problems. The relevance of scaling exponents and scaling near phase transitions to computer science problems will be elucidated. In NP-complete problems, current algorithms require a computational time which grows exponentially with system size. In addition, there is a peak in the computational time at characteristic parameter values, and these special points share many features with phase transitions in quenched random media. A variety of application of P algorithms to physics problems have become important. The relevant P problems and their applications to physics problems will be presented. Finally the impact of quantum computing on random combinatorial problems will be outlined and two important quantum procedures, Shor's algorithm and Grover's algorithm, will be described.

The lectures on replicas will assume that participants have worked through the classic Sherrington-Kirkpatrick paper on the infinite range spin glass Phys. Rev. Lett. 35, 1792 (1975). Detailed notes on this calculation will be posted prior to the course, along with some introductory exersizes covering background material for the course.

There is no registration fee for the course, but people should send an email to , if they plan to attend.

Schedule - Lectures are in rm 4270 BPS

Lectures will occur Friday, Saturday, Sunday, Monday, Tuesday and Wednesday Mornings of 10-15 May inclusive.

9 - 10:10am Remi Monasson

10:10 - 10:30am Break

10:30 - 11:30am Phil Duxbury

Outline of Monasson's Lectures

1. The random graph: presentation, relationship with the Potts model, the percolation transition, and large deviations. (the aim is to give a rather simple introduction to functional order parameter before applying the same techniques to spin glass models). [one lecture]

2. Spin models on the Bethe lattice and random graphs: Ising model on fixed connectivity trees, cases of fluctuating connectivities, and multi-spin interactions. (this is an introduction to RS theory and the cavity approach for spin models on sparse graphs). Formalism for Replica symmetry breaking theory; resolution using cavity equations and/or variational calculations; Application to the multi-spin ferromagnetic and disordered spin models. [one and a half lecture]

3. The covering of random graphs. Presentation of the problem; Mapping onto a statistical mechanics model; Small connectivity results; RS theory; Comparison with exact results (bounds, analysis of algorithms). [one and a half lecture]

4. The satisfiability of random Boolean Formulas. Presentation of the problem; Analysis of the phase transition (nature of the transitionm, structure of solutions, ...); Computational complexity aspects (analysis of solving algorithms using statistical mechanics). [two lectures]

Here is a complete write-up of the application of the replica method to the K-SAT problem. This fills in the details that Professor Monasson did not have time to cover during his lectures.

Here are some exersizes to get used to the ideas and notation of the course

This is the details of the Sherrington-Kirkpatrick RS solution to the infinite range, Gaussian, spin glass. Some of the details of Parisi's RSB solution are also here.

Outline of Duxbury's Lectures

1. Relations between algorithms and physics. Minimum spanning tree(MST) and shortest path. Mapping to invasion percolation and DPRM. Proof of universality of MST. Prim and Dijkstra algorithms. [1 lecture]

2. Matching methods and applications to spin glasses in two dimensions and to rigidity percolation. Exact constraint counting using bipartite matching. Rigidity of Cayley trees.[1.5 lectures]

3. Flow algorithms. Minimum cut/maximum flow and minimum cost flow. Applications to manifolds, random magnets and to the analysis of flux arrays. RFIM on complete graphs and trees. [1.5 lectures]

4. The relevance of Quantum algorithms. RSA encryption. Shor's algorithm for factoring. Grover's algorithm for unstructured search.[2 lectures]


A lot of the material for items 1-3 above will be taken from M.J. Alava, P.M. Duxbury, C.F. Moukarzel and H. Rieger, ``Exact combinatorial algorithms: Ground states of disordered systems''. Volume 18 of Phase transitions and critical phenomena, Domb and Lebowitz eds., (Academic Press, 2001).

A very good place to start reading about quantum algorithms is John Preskill's lecture notes which are on the www at,

Document last modified May 6th 2002