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 email@example.com , if they plan to attend.
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).
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.
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 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