SISSA
ISAS
Scuola Internazionale Superiore di Studi Avanzati
International School for Advanced Studies
Statisti al me hani s of spin systems
on diluted random stru tures
Thesis submitted for the degree of
Do tor Philosophi
Candidate: Supervisors:
Mi hele Leone Prof. Amos Maritan
Introdu tion 7
1 General te hniques for diluted random models 11
1.1 Graphs and Hyper-graphs: preliminaryde nitions . . . 11
1.2 Spin models ondiluted stru tures . . . 14
1.2.1 Disorder . . . 15
1.2.2 Frustration . . . 15
1.2.3 Combinatorialoptimizationproblems as spin models . . . 18
1.2.4 Quen hed disorderaverages and general omputational strategies . . . . 19
1.2.5 Repli as . . . 19
1.2.6 Cavity . . . 21
1.2.7 Phase spa e stru ture . . . 23
2 The generalized diluted p-spin model 27 2.1 Combinatorialoptimizationinterpretation of p-spinmodels: the XOR-SAT . . . 28
2.2 From the partitionfun tion to the average free-energy. . . 30
2.2.1 Some onsiderationson normalization. . . 34
2.3 The Repli a Symmetri Results . . . 37
2.3.1 Vanishing elds . . . 39
2.3.2 Analyti al Ansatz for T =0 solutionswith non vanishing elds. . . 40
2.3.3 The ferromagneti solution . . . 41
2.3.4 The spin-glass statesand the RSenergy lines . . . 44
2.4 The 1RSB al ulations . . . 45
2.4.1 The variationalfa torizedAnsatz . . . 47
2.4.2 The onstru tion of the phase diagram . . . 51
2.4.3 On the physi alir-relevan e of fra tional elds . . . 58
2.4.4 A parti ular exa t ase: hyper-graphs with xed degree distribution . . . 60
2.5 The general 1RSBequations . . . 65
2.5.1 General SolutionatT =0 . . . 67
2.6 "Ferromagneti omplexity" . . . 73
2.6.1 Hiding solutions inrandom satis abilityproblems . . . 76
2.7 An exa t alternative solutionof the p-spin modelat T =0 . . . 78
2.7.1 The onset of frustration: hyper-loops in the graph . . . 78
2.7.2 Leaf removalalgorithm . . . 79
2.7.3 The ore and the al ulation ofthe threshold . . . 83
3 Some parti ular ases of interest 89
3.1 The 2+p-XOR-SATmodel: role of phase oexisten e and nite-size s aling . . . 89
3.1.1 Model de nition and outlineof someresults . . . 90
3.1.2 Numeri al simulations . . . 92
3.1.3 Con lusions . . . 95
3.2 Ferromagneti orderingon randomgraphs . . . 96
3.2.1 Introdu tion . . . 96
3.2.2 The repli a approa hon generalrandom graphs . . . 97
3.2.3 Ferromagneti phasetransition . . . 99
3.2.4 Criti al behavioraround . . . 100
3.2.5 Power lawdistributed graphs . . . 101
3.2.6 2< 3 . . . 102
3.2.7 3< 5 . . . 103
4 Two examples of NP optimization problems 105 4.1 The Hyper-Graph Bi oloring Problem. . . 105
4.1.1 The RS results . . . 106
4.1.2 The RSB Cal ulations . . . 108
4.2 Results of the variationalRSB al ulations for the random 3-SAT . . . 111
5 Phase and omputational omplexity transitions 115 5.1 Global algorithmstransitions inlinear systems over nite elds. . . 115
5.1.1 Introdu tion . . . 115
5.1.2 Random Linear systems in GF(2): rigorous results and statisti al me- hani s analysis . . . 116
5.1.3 Algorithmsbehavior . . . 120
5.1.4 The RSA ryptosystem and fa torization . . . 123
5.2 The dynami phase transitionfor de oding algorithms. . . 132
5.2.1 Introdu tion . . . 132
5.2.2 Error orre ting odes, de oding algorithmsand the avity equations . . 133
5.2.3 Statisti alme hani s formulationand the repli aapproa h . . . 138
5.2.4 Binary erasure hannel: analyti al and numeri alresults . . . 139
5.2.5 The general hannel: analyti al and numeri alresults . . . 147
5.2.6 Con lusions . . . 154
6 Determining bounds 157 6.1 Variationalbounds for optimizationproblems and spin systems. . . 157
6.1.1 Notations . . . 158
6.1.2 The general strategy . . . 160
6.1.3 The RS bound . . . 164
6.1.4 The 1RSB Bound . . . 168
6.1.5 Summary and on lusions . . . 171
Con lusions and perspe tives 173
C On the hoi e of the fun tional order parameter 179
C.1 The degree sub-distributions: an alternative al ulation . . . 181
C.1.1 RS results . . . 181
C.1.2 Fa torized 1RSB results: 1 . . . 181
C.2 Fa torized 1RSB results: 2 . . . 182
D Criti alexponents and non universal amplitudes 183 D.1 Case <k 4 > nite . . . 183
D.2 S ale free networks: ase 3< <5 . . . 184
E E.C.Codes: BSC, A T=0 variational al ulation 187 F Details of the al ulations of Chapter 6 189 F.1 p-spin . . . 189
F.1.1 Che k of the positivesign of R p spin 1RSB . . . 189 F.1.2 Che k of F p spin var [P℄=F p spin 1RSB [P℄ . . . 191 F.2 K-SAT . . . 192
F.2.1 Che k of the positivesign of R K SAT RS ... . . 192 F.2.2 ...and of R K SAT 1RSB . . . 194 F.2.3 Che k of F K SAT var [P℄=F K SAT 1RSB [P℄ . . . 195
F.2.4 Existen e of the free-energy of the p-spin model . . . 196
Bibliography 204
Random ombinatorial problems and diluted spin systems
During the last two de ades, in spite of many pioneering fundamental ontributions ([1℄ and
referen es therein), the mainstream ofanalyti alresults inthe eld of statisti alme hani s of
spin-glasses anddisorderedsystems fo usedmainlyonmean- eldmodelsof largedegree
1
([2,3,
4, 5,6℄ and referen es therein).
Inthe morere entyears, amajor e orthas been devoted tothe study ofmodels that ould
retain,atleastinastatisti alway,somefeatures of nitedimensionality,like nitedegrees and
presen e of geometri al onstraints in uen ing both the stati and the dynami al properties
of the systems. Spin glass models over diluted random graphs onstitute by now the natural
frameworkforthemostadvan edanalyti alstudies on erningtheglasstransitionindisordered
systems.
The interest in diluted spin system is by far not limited to physi s. As we shall dis uss
in great detail in this thesis, there exists a huge lass of open root problems in theoreti al
omputer s ien e and in dis rete mathemati s whi h have a simple representation as diluted
spin system.
From the point ofview of pure physi s,the study of dilutedsystems represents onlya rst
step towards the treatment of nite dimensionality or geometri ally stru tured models, and
one ould think for instan e to even more omplex or \semi-random" stru tures where some
regularity reminis ent of a real latti e geometry is progressively introdu ed into the random
adja en ymatrix. Buteven ifonelimitstheinvestigationtopurelyrandomdilutedgraphsand
to lassi al spin models de ned onthem, the questions that arise are still of a deep kind both
from afundamental and froman appli ationoriented pointof view.
Why are this models interesting? The main reasons an be summarized inthe following:
Fromafundamentalpointofview: theyarestillessentiallymean eld,howevertheyretain
nite intera tion degrees that isreminis ent of nite dimensional ases. The presen e of
large s ale stru tures like large loops has to be taken into onsideration as a rst step
in the understanding the role of topology and geometry for the olle tive behavior of
omplex systems.
Moreover, they are widely a epted as prototype models in the study of fundamental
phenomena inthe theory of ComputationalComplexity.
From an appli ative (but not less important) point of view: they have a natural wide
range of appli ations toa lass of systems that span over the following elds
1
Inthefollowingwe will all degreewhat usuallyphysi ists all onne tivity, i.e. thenumberof neighbors
of avertex ofthe latti eorgraphthemodel isde ned on. We hose The rsttermin order to be onsistent
{ Statisti al analysis of the behavior of realisti neural networks ([2, 6, 27, 28℄ and
referen es therein)
{ Combinatorial optimization problems ([27, 29, 30, 31, 32, 34, 35, 36, 37, 117℄ and
referen es therein)
{ Error orre ting odes and ryptography ([27, 38,39℄ and referen es therein)
{ Models of statisti al information pro essing and image restoration ([27℄ and
refer-en es therein)
{ Statisti almodelsof olle tivephenomenainbiology(forinstan e. geneandprotein
regulatory networks, networks of ellular signalling pathways et .) ([40, 41℄ and
referen es therein)
{ Statisti al analysis and optimal design in omplex arti ial networks su h as the
Internet or the World Wide Web ([43, 44,45,46℄ and referen es therein)
In whatfollowsweare goingtodeal both withbasi theoreti alaspe ts and withsome
spe- i appli ations belonging to omputer s ien e ( ombinatorial optimization, error orre ting
odes and ryptography). We are going to study the low temperatureequilibrium and
out-of-equilibriumphasesofdilutedspin-glasses withthe aimof elu idatingthe geometri alstru ture
of ground states underlying stati and dynami transitions. The omputational ounterpart
of su h a study arises from the elementary observation that (hard) ombinatorial
optimiza-tion problems an beeasilyreformulatedasproblems of ndinggroundstatesinspin-glass-like
Hamiltonians. In this sense the idea of studying their topologi al stru ture is quite a natural
one [2℄. The re ent e orts in developing a mathemati al and physi al understanding of su h
systems over diluted stru tures have opened new perspe tives and new roads to solutions to
those problems, ta kling them in their natural milieu. The models reviewed and studied in
this thesis are all of random nature. While this is usually the most natural thing to do in
physi s, the study of random ombinatorial problems has been revealing itself useful also in
omputer s ien ewhereitallows tobroaden tothe typi al- asethe lassi alworst- ase notions
of omputational omplexity [34℄.
This thesis isdevoted tothe analyti al study of the dynami and stati transitions
numer-i allyobserved in this whole lass of models, withspe i fo us on ombinatorialoptimization
problems and error orre ting odes, on e mapped on spe i diluted spin systems. Stress is
posed on the onne tion between the slowing down pro esses in algorithms behavior and
sta-tisti alphase transitionsdue tosome intrinsi property onthespin model, that anusually be
tra ked down to the emergen e of non trivial frustrated topologi alstru tures in the
underly-ing graph. The re ent a hievements [29, 30, 56℄ of a promising new lass of algorithms that
seems to outperform the other state-of-the-art sear h pro edures for typi ally hard
ombina-torial problems are based ontheoreti al understanding rooted inthe on epts reviewed in this
work. This result, among others, seems to show how statisti alphysi s of disordered systems
has stillalot totea h uswhen appliedto the eld of omputational omplexity.
The thesis willbe organized inthe following way: in the rst hapter some general
guid-ing on epts of random graphs and modern statisti al physi s of disordered systems will be
presented, and the onne tion with relevant problems in theoreti al omputer s ien e will be
stressed. In hapter two wewillintrodu eindetailthe mathemati alte hniquesused todeal
with the analyti omputation of relevant physi al quantities for a wide lass of spin models
arbi- omplete al ulations will be shown in the ase of a generalization of the p-spin model over
su h stru tures. Their validity an be seen to hold for a mu h wider family of random
om-binatorial optimization problembelongingto the NP lass in the worst ase, su h as K-SAT,
Q- oloring[57, 58℄ and many others. Some appli ations to spe i prototype examples will be
shown inthe third hapter, while hapter four willdeal with spe i examples oftwo
om-binatorial optimization problems, namely the 3-SAT and the bi oloring problem of graphs of
uniform rank 3
2
. Chapter ve will be devoted to two relevant examples of the relation
be-tween the algorithmi omputational omplexity of a problem and the presen e (and nature)
of dynami and stati phase transitions in the asso iated spin model. In the rst example
the mapping will essentially be between the sear h for solutions of large random sparse
lin-ear system over nite elds
3
and the sear h of the zero temperature ground states of some
ad ho de ned multiple rank intera tion diluted ferromagnet. In the se ond part essentially
the samemapping willbe used tostudy the dynami slowing down of parity he k algorithms
for error orre ting odes - with the onsequent onset of omputational omplexity - and the
orrespondent dynami phase transitionin spin glasses.
The mathemati al language used throughout this work will be that of repli a theory: we
are well aware that this is a very ontroversial eld, due to the lankness of lear and rigorous
foundations that makes its mathemati alinterpretationobs ure and its results \unreasonably
su essful"[42 ℄. And this even after more than 20 years after the original formulation of the
theory [59℄. Inthe ne essary attempttoover omethis problema al ulationin hapter sixis
presented withtheaimofshowinghowrepli atheory anbeatleastinterpretedasasystemati
variationalmethodalsointhe aseondilutedmodels. Thetreatmentwillbeageneralizationof
the methodre entlyproposedbyGuerra[60℄forfully onne tedmodels. Moreover, veryre ent
work[23,24,30℄has lari edtheequivalen ebetweenthe avitymethodandthe repli aresults
also in the diluted systems ase. Sin e the rst one deals with usual probabilisti obje ts, it
has a learer and more dire t interpretation that ould lend itself to further rigorous studies.
Some dire tions for future work are summarized in the on lusions.
The al ulationsand theresultspresented inthisthesisare theoutputofathreeyears
ollabo-rationwiththeI.C.T.P. ondensedmatterandstatisti alphysi sgroupinthenamesofRi ardo
Ze hina,SilvioFranz,AlfredoBraunsteinand Federi oRi i-Tersenghi(nowinRome). Great
partoftheworkwasalsotheoutputofa ollaborationwithAndreaMontanari(
E oleNormale,
Paris). Thisworkwouldnothavebeenpossiblewithoutthem,andIwishtothankthemdeeply.
2
thede nitionofgraphandofrankwillbegivenatthebeginningof hapter1.
Disordered Diluted Spin Systems
Connection to Random
Combinatorial Optimization
for one class of models
Detailed replica calculation
Alternative solutions in
one specific case
The RS and 1RSB pictures
CHAPTER 2
Detailed Calculations
General Concepts:
CHAPTER 1
CHAPTER 6
Rigorous results
Bicoloring and 3−SAT
CHAPTER 4
Ising model on arbitrary
degree networks
structures
Models on heterogeneous
CHAPTER 3/5
Random Graphs and Hyper−graphs
Replicas
Transitions in Global Algorithms
Error Correcting Codes
APPLICATIONS
CHAPTER 5
General te hniques for diluted random
models
1.1 Graphs and Hyper-graphs: preliminary de nitions
Duringthe wholelengthof thisthesis weare goingtodeal withspin models de ned ondiluted
random stru tures su h as simple random graphs or hyper-graphs [61, 62, 63℄. A graph G is
ommonlyde ned asanon-empty nitesetV(G)ofelementaryunits alledverti es ornodes
or sites inour ommonnotation, and a niteset E(G) of distin t unorderedpairs of distin t
nodes alled edges or links . We allV(G)the vertex set and E(G)the edge set of G. In our
notationthe i
th
site willbe denoted by itsLatin index i andanedge between sites iand j will
bedenoted as the ouple ij. We willwork with undire ted edges (graphs). Wewill de ne the
size or orderof the graph asthe ardinalityof the vertex set or the number N of sites, we will
allM the the ardinalityofthe edge set. A omplete graphisagraphwhose edgeset ismade
of all possible links between nodes. In that ase one has M = N(N 1)=2 O(N
2
). Many
interesting models an be de ned on a generalization of graph stru tures that go under the
nameofhyper-graphs. LetX=fx
1
;::::;x
N
gbea niteset., andletE =fE
i
ji2Igbeafamily
of subsets of X. E is said to be a hyper-graph on X if E
i 6= ; 8 i 2 I and S i2I E i = X. The
stru ture H = (X;E) is alled hyper-graph. Again, jXj = N is the order of the hyper-graph.
It is easy ro see how a graph is simply a parti ular ase of hyper-graph with E restri ted to
subsets ofexa tlytwoelements. E willbe the generalizededge set (orhyper-edgeset) of H . Is
it possible to draw a hyper-graph in many equivalentways. One possibility is shown in gure
(1.1),whereedgesareshownasmultipleverti esplaquettes. Thismaynotbetheorthodoxway
to represent ageneral hyper-graph, but is reminis ent of the usualway torepresentmulti-spin
orplaquetteintera tioninlatti e eldtheoryorstatisti alme hani s,sowewilladoptitinthe
following. In the future hapters we willo asionallyneed the on ept of in iden e matrix as
the matrix
^
A=((a
j
i
))with M rows thatrepresent the edgesof Hand N olumnsrepresenting
its verti es, su h that:
a j i = 1 if x j 2E i a j i = 0 if x j = 2E i
In a hyper-graph H , the rank r(S)of a set S X is de ned as
r(S)=max
i
jS\E
i
E
E
E
E
E
9
10
11
8
7
E
E
E
E
E
E
E
E
E
E
1
E
2
4
3
5
E
6
E
1
E
2
3
4
5
4
5
E
2
E
1
3
6
7
8
E
E
E
Figure1.1: Trivialexamplesof asimplegraph,two hyper-graphs of xed rank3and an
hyper-graph of rank4 and minimalrank 2. alsorank 2edges are expressed in hyper-graph notation.
All theseexample haveN verysmall ompared with the stru tures wewillbe interested in,so
they are onlyto be intended, alongwith others in the text, as api torial guide.
The rank of the hype-graphis therefore
r(X)=max i jX\E i j (1.2) Ifr(X)=E i
8i, thenthe hyper-graph issaid tobeof uniformrank. Asimple graphwillthen
be a hype-graph of uniform rank2.
Toea hhyper-graphH=(X;E
1
;:::;E
M
)there orrespondsadualhyper-graphH
=(E;X 1 ;:::;X N )
whose verti es arepointse
1 ;:::;e M representing E 1 ;:::;E M
and whoseedges are setsX
1 ;:::;X N representing x 1 ;:::;x N where8j, X j =fe i jiM ; E i 3x j g (1.3)
When dealing with the graphi al interpretation of error orre ting odes, we will swit h to a
representation of hyper-graphs interms of fa tor graphs [64, 65,66℄(see alsothe appendix for
a graphi alexample),more familiarto omputer s ientists, and where duality is madeevident
and expli itlyexploited. Any hyper-graph an bereadasabipartitegraphwhereone subsetis
X andtheotherE,andwherethereisaedgepointingfromx
i
toe
l
ifthe orrespondentelement
ofthe in iden e matrixofthe originalhyper-graph isnon-zero. Su hparti ular bipartitegraph
is alledfa tor graph. Given a hyper-graph H , a hain of length q isde ned [63℄as asequen e
(x 1 ;E 1 ;x 2 ;E 2 ;::::;E q ;x q+1 ) s.t. x 1 ;::::;x q
are distin t verti es
E
1
;::::;E
q
are distin t edges
x k ;x k+1 2E k 8 k =1;:::;q
In the physi s jargon, hainsare nothing but onne ted omponentsof the hyper-graph H .
rank 2is nothingbut aloop. Inthe physi s of disorderedand frustratedsystems a parti ular
role turn out to play those y les where every vertex belongs to an even number of edges.
We will all those y les \ ompa t y les" , \hyper- y les" or \hyper-loops", for the similarity
with the graphs ase where loops always have this property. Two examples of very parti ular
y les (the rst is alsoa ompa t y le) are shown in g. (1.1) forthe ase of ahyper-graph of
uniformrank3(see also[19℄for the rst appli ationtohyper-loops on epts tospinglasses, to
myknowledge). A hyper-graph isthe said toberandom[62, 69,68℄wheneverthe presen e or
absen e ofea hof itsedgesisgiven with ade nedarbitraryprobability. Traditionally,random
graphs were introdu ed as those where the probability of having an edge between two given
verti es is a onstant r
1 :
8i;j Prob(ij 2E(G))=r (1.4)
If r/ O(1) then the graph is said tobedense as wellas its in iden e matrix. If r/O(1=N)
then the graph willbe thin or diluted and its in iden e matrix willbe a sparse one. In this
last ase M / N. This will be the ase we'll onsidered it the rest of the thesis. Complete
hyper-graphs of nite rank l have C
N l / N l 1 edges 2
. Therefore, in order to have a number
of edges proportional to N every plaquette ontaining l, verti es must have a probability to
be present proportional to 1=N
(l 1)
. If ea h edge is present with the same xed probability,
properly res aled with N, the hyper-graph will be diluted and ea h vertex i will have a nite
degree k
i
drawn from apoissonianprobabilitydegree distribution
k =e k k! (1.5)
where isafreeparameterdeterminingmeanvalue andvarian eofthe distribution. A
parti -ular \self similar" form is pe uliar of the poissoniandistribution: In this ase the probability
k
of nding a vertex of degree k is equal to the probability q
k
of nding a nearest neighbor
vertex with degree k+1, as an be seen applyingeq. (1.5) tothe de nition [69℄
q k (k+1) k+1 P k k k = (k+1) k+1 <k > : (1.6)
This note is very important in pra ti al al ulations and is the origin of major simpli ations
inthe repli aandthe avity equations[23,24℄wewillseelater on. Thisisre e ted by thefa t
1
Averyri hphenomenologyofstru turesappearinginthegraphasafun tionofthedegreeanda omplete
study of graphsbehaviorasr in reases withN hasbeen performed on arigorousmathemati a basisstaring
from the seminal paper of
Erdos and Renyi[61℄. Forasystemati introdu tionsee for instan e [62℄ and [67℄
and referen estherein. Tomyknowledgeno omparablesystemati study hasbeenundertakenin the aseof
rank>2hyper-graphsyet. Fora learintrodu tionto hyper-graphssee[68℄.
2 C
N
that in the poissonian ase the mean value uniquely determines the varian e and vi e-versa.
As a onsequen e, a lot of simpli ations and parti ular behaviors of poissonian hyper-graphs
annot be applied in wider families of random stru tures. However, itis possible to onstrain
the probability of the value of the number of edges in ident on a xed vertex in order to
draw diluted hyper-graphs from ensembles with arbitrary degree distributions (arbitrary
k ).
The onstraints will be of global nature and will not introdu e vertex-vertex orrelations, as
it will be seen in the following. Sin e the repli a as well as the avity equation for spin
models de ned over diluted hyper-graphs will be on erned in the omputation of the lo al
e e tive elds a ting on ea h spin variable in absen e of a parti ular edge in ident to the
vertex under onsideration, The natural ensemble we are going to work with will indeed be
that of the q
k
and not that of the
k
. We stress again that this hange is immaterial in the
poissonian ase, where one falls ba k into the same ensemble, but not in the general one.
Moreover, one ould of oursethinktomore omplex or\semi-random"stru tures wheresome
regularity reminis ent of a real latti e geometry is progressively introdu ed into the random
matrix through the presen e of orrelations of various kind (see [41℄ for one among possible
examples) or through the presen e of regular sub-hyper-graphs merged in the whole one in a
random way. But even if one limits the investigation to purely random diluted hyper-graphs
and tosimple lassi alspin models de ned onthem,the questions thatarise are stillof adeep
kind both from a fundamental and from an appli ation oriented point of view. Nevertheless,
theimmediatefuturedire tionsforinvestigationswillne essarilyhavetodealwiththepresen e
ofsu h orrelations[72,46,70,71,73℄,aswellaswith modelswheretheintera tion onstraints
are non lo alin nature[74℄ or non purely lassi al.
1.2 Spin models on diluted stru tures
In all ases, we are going to work with models that an be des ribed, under appropriate
map-ping, via some spin Hamiltonian H(J;s), where fJg represents an ensemble of disordered
intera tion energy variables taking non zero values onthe edges of the hyper-graph orde ned
as ombinationsofmoreelementaryintera tion termsasinthe aseoftheK-SAT. s)are N 1
spinvariables(0or1Booleanvariablesintheusual ombinatorialproblemsen oding)livingon
the verti esofthe hyper-graph. Wewilldealinthefollowingwith ases wheretheHamiltonian
an bewritten asa sum of lo al energeti ontributions
as H(J;s)= X (fJ g;fs g); (1.7)
whereindi atesea hsubset(usuallyanedgeoftheunderlyinghyper-graphora lauseinSAT
-likeformulation)that ontains asmallnumber of both onstraintsand spin variables, relative
to the total number N of variables
3
. As atitle of example,the simplest possible Hamiltonian
is the Viana-Bray (see the original arti le by Vianaand Bray in[1℄):
H(J;s)= X i<j J ij s i s j : (1.8)
The diluted hyper-graphs that de ne the underlying topologi alstru ture will be drawn from
the appropriate hosenstatisti alensemble, fullydeterminingtheprobabilitydistributionP(k)
3
of edge degrees and the probability distributionQ(l)of ranks. The rankonea h single
hyper-graphedgeisequalinthe asesunder onsiderationtothenumberofspin variablesinthe lo al
energeti term
. Therefore the distributionQ(l) isgoingto bestri tly relatedtothe fra tion
of l-variables intera tion terms Hamiltonianssummingup to the total H(J;s)
4 .
1.2.1 Disorder
On e the set fJg of non zero ouplings (equivalent to the set of present edges) is set, its
elements an take values a ording to an a priori arbitrary distribution (J). For disordered
pure ferromagneti -typemodels (J)willread
(J)=Æ(J
^
1): (1.9)
For disordered pure anti-ferromagnets
(J)=Æ(J+
^
1): (1.10)
Finally, forthe pure generalized1 spin-glass ase
5 : (J)= 1 2 Æ(J ^ 1)+Æ(J+ ^ 1) (1.11)
More in general, the same models an be studied for other forms of the oupling distribution
(J): ontinuous,mixturesofa ontinuousandadeltapeaked part,mixturesof pure
ferromag-neti and spin-glassterms,andsoon. In hapter5wewillworkwith modelsthatareoriginally
de ned asa mixture of the previous ferromagneti and spin-glassone
(J)= 1 2 pÆ(J ^ 1)+(1 p)Æ(J+ ^ 1) (1.12)
where p is a parameter tuning the amount of \average frustration" or \average glassiness"
present into the system. Finally,the rigorousresults presented in hapter6 willbe derived for
general formsof symmetri (J).
1.2.2 Frustration
It was observed right at the beginningof spin-glasstheory by Toulouse[2, 75℄ that a mixture
of ferromagneti and anti-ferromagneti ouplings an give rise to on i ting onstraints,su h
that it is in general impossible to minimize lo ally all the energy terms
. This property
is widely known as frustration. In spin glass-models on diluted stru tures (Viana-Bray), this
typi allyhappens when the density of the graph allows parti ular ompa t stru tures su h as
loops to per olate in the system. In the ase of higher rank hyper-graphs, loops per olation
turns outnot tobeasuÆ ient ondition forthe existen eof anextensive fra tionoffrustrated
onstraints,essentiallybe ause the extra degrees of freedomdue tothe possibilityof adjusting
the spin variables belonging to the edges but not to the loop. In fa t, even more ompa t
stru tures su h as hyper-loops must per olate in the underlying matrix. The phenomenon is
exempli ed in g. (1.2). The ommon presen e of disorder and frustration allows for a phase
4
Infa tthetwofra tionswill oin ideinthegeneralizedp-spinmodel.
5
Histori allythespin-glassmodelshavebeende nedonlyinthe aseoftwobodyintera tions,asaphysi ally
sensible model for real magneti materials. However,a generalizedmulti-spin intera tionfamily of spin-glass
type models anbejusti ed notonly fortheir usein random ombinatorial optimization, but asane e tive
−
−
+ +
+
+
+
+
−
−
−
(unsatisfied)
+
+
−
+
+
+
?
to satisfy the constraint
one can always choose
frustrated
constraint
or
?
=
hyper−loop
+
−
Figure1.2: Frustration ingraphs and hyper-graphs. This Pi ture isvery similartothe one we
will draw in hapter 2 for the ore resolution under the a tion of the Leaf Removal algorithm
(see se tion 2.7 for details). It is important to keep in mind this similarity, be ause it will be
the main ause of the e e tiveness of the algorithmin lo ating the spin-glasstransitionin the
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
Figure1.3: Pi torial one dimensional proje tion of rough energy lands ape.
spa estru ture withalarge-typi allyexponential-numberofdegenerateglobalgroundstates
as well as de nite energy metastable states. Pi torially, one ould think that these systems
show an energy lands ape of the kind exempli ed in g. (1.3). This pi ture is however often
verymisleadingbe ausethex-axisinthe pi tureis infa taproje tion ofthe highdimensional
phase spa e, where all the topologi al stru ture is hidden. The degree and nature of the
inner stru ture of the phase spa e an vary in prin iple from problem to problem. A better
understanding of thistopologyinthe aseof some modelsinterestinginrandom ombinatorial
optimization, oding theory and more in general disordered systems physi s, is the main aim
of the present work.
We would like to mention that the families of models studied in the following hapters is
by no means exhaustive. For instan e, a natural generalizationof the te hniques explained is
urrently been appliedto Potts-likemodels[76℄ and ouldbeadapted in prin ipleto Classi al
Heisenberg models and so on. However, in these last ases, the te hni al al ulations are
more involved [57, 58℄ be ause, as it turns out, one is for ed to work with fun tional order
parameters whi h an be written as distributions of e e tive lo al elds of ve torial instead
of s alar nature, as it is the ase of the examples treated in the present work. This leads
to self onsistent equations for the order parameters that are inter-wined in the various eld
omponents [58℄
6
. The body of the hapter will deal with the analyti al repli a te hniques
devised to omputethermodynami alquantitiesofphysi alsystemsondilutedhyper-graphsin
absen eof orrelationsandinpresen eofquen heddisorder. Letusnowexpli itthe onne tion
between this lass of models and ombinatorialoptimization theory.
6
The oloringdegreestati thresholdobviouslydepend onthe numberof olorsavailable for the oloring,
at xed graph. The urrently best rigorous upper bound forthe 3-COL/UNCOL transition (three olors) in
poissoniandegreedistributed randomgraphsis5:06[77℄. Itwasobtainedusingare ned rstmomentmethod,
equivalent to an improved annealed approximation in statisti al physi s. The RS 5:1 threshold obtained in
[57℄ ex eeds the rigorous bound, while at the 1RSB level the authors of [58℄ were able to nd a dynami al
threshold foranaverage degreeequalto 4:42,followedby the3-COL/UNCOLtransition at 4:69. The values
are onje turedtobeexa tbytheauthors, andareindeed inverygoodagreementwithnumeri alsimulations
[78℄. Thegeneraldis ussiononthemeaningofthedynami al thresholdis donein hapter2. Noti ealso that
1.2.3 Combinatorial optimization problems as spin models
Classi al omplexitytheory[34℄,asarisingfromCook'stheoremof1971[47℄,dealswiththeissue
of lassifying ombinatorialoptimizationproblemsa ordingtothe omputational ostrequired
for their solution. The hard problems are grouped in a lass named NP, where NP stands for
`non-deterministi polynomial time'. These problems are su h that a potential solution an
be he ked rapidly whereas nding one solution may require an exponential time in the worst
ase. In turn, the hardest problems in NP belong to a sub- lass alled NP- omplete whi h is
at the root of omputational omplexity. The ompleteness property refers tothe fa t that if
an eÆ ient algorithm for solving just one of these problems ould be found, then one would
have an eÆ ient algorithm for solving all problems in NP. By now, a huge number of
NP- omplete problemshavebeen identi ed[34℄, andthe la kofaneÆ ientalgorithm orroborates
the widespread onje ture that NP6=P, i.e.that nosu h algorithmexists.
Complexity theory is based on a worst- ase analysis and therefore does not depend on
the properties of the parti ular instan es of the problems under onsideration. In pra ti e
algorithmsdisplaya huge variabilityof runningtimes, rangingfromlinear toexponential,and
therefore a theory for their most probable behavior represents the natural omplement to the
worst- ase s enario.
The most ommonproblems en ounteredin omputer s ien eand issue of theoreti al
anal-ysis studieswithin omputational omplexity theoryare of atype. A de ision-makingproblem
isoftenformulatedasthatofthe maximizationorminimizationofamulti-variablefun tion,an
optimization problem
7
. The fun tion tobe minimized(maximized) is alled obje tive fun tion
or ost fun tion, and basi ally ounts the number of violated onstraints , given a parti ular
on gurational assignmentsto the variableson the problem. An exampleof ombinatorial
op-timizationproblemfamiliarto physi ists is that of ndingthe ground state of anIsing model.
More ingeneral,any sear h ofgroundstates inanyspin modelonagiven geometri al or
topo-logi al stru ture an be seen as parti ular optimization problem. On the other hand, a large
lass of purely ombinatorial optimizationproblems in prin iplenot related tophysi s an be
seen equivalent to the sear h for zero temperature ground states of ad ho onstru ted spin
models (often spin-glasses) on parti ular topologi al stru tures. Among others we an ount
the number partitioning problem, the graph partitioning, the graph and hyper-graph
olor-ing, the knapsa k problem, the s heduling problem and the satis ability (SAT) one. A lear
overview ofsome ofthese examples an beseen in[27℄ andanintrodu tiontothe study
statis-ti al me hani sstudy ofrandom ombinatorialoptimizationproblems seenasspinsystems an
be found in [35℄. In parti ular, SAT has been extensively studied due toits NP- ompleteness
and general nature. Its mapping on a parti ular spin-glass model has been elu idated in [9℄.
As well as in many of its variations, the SAT ost fun tion an be read as the olle tion of
M logi al onstraints that have to be satis ed by N boolean variables. It turns out [9℄ that
any SATformula ost fun tion an bewritten asthe Hamiltonianofa spin modelwhere0 1
variables arerepla ed by 1spins, andthe onstraintsare welldetermined olle tionsof edges
orplaquettes of various rankof agiven hyper-graph that ompletely hara terizes the formula
under study. If M O(N), whi h is the ase the most interesting formulas belongs to - i.e.
those losetothe satis abilitythreshold- thenthe underlyinghyper-graph isadilutedone. In
ordertostudy theSATprobleminitsspin-glassformulationitisthereforene essary todevelop
ageneralformalismtobeabletodealwithtopologi alstru turessu hasdilutedhyper-graphs.
7
In the followingthis willbe expli itlydonefor the ase of the generaldiluted p-spinlike
mod-els, but it will be then further generalized in order to ta kle problems like the K-SAT one.
Whenever the onstraints forming the formulato be satis edare drawn randomly froma
pre-viouslyde ned ensemble, thenthe optimizationproblemwillhavearandomnature. Insteadof
working on a parti ular hyper-graph, this willamount to averaging over the hosen ensemble
of\quen hed"stru tures. Itwillbetheninterestingtodis ernwhi hproperties(oneforallthe
inner omplexity of the problem) survive in shifting the sear h for solution from a parti ular
to a random ase. The following hapters willalmost allbe devoted tothe appli ation of the
general analyti al te hniques developed here to various optimization problems, some of them
used astoy models, asin hapter3, someothers ofmore omplexanalysis, asinthe remaining
hapters.
1.2.4 Quen heddisorder averages andgeneral omputational
strate-gies
Evaluation of a physi al quantity using a spin Hamiltonian of the type (1.8) or any more
ompli ated ase onsidered in this work starts from the tra e over the spin variables for a
given xed(quen hed)set of ouplings. Forus,this orrespondstorandomly hoosingadiluted
hyper-graphfromadesiredensembleanda xedformofthe(J). Thefree-energyofthesystem
F[J℄= 1 logTr s e H(J;s) (1.13)
an be harmlesslyaveragedoverthe quen hed disorderinthe thermodynami limit,ifthe
self-averaging ondition overextensive thermodynami alquantities (like indeedthe free-energy)is
satis ed as we assume to be true throughout the whose treatment. This averaging pro edure
goesunder the name of on gurationalaverage :
hFi
Z
D(J)F[J℄ (1.14)
However, the dependen e ofthe partitionfun tiononJ isingeneralvery ompli atedanditis
noteasyto al ulateexpression (1.14)dire tly. Moreover, inthe aseofrealworld optimization
problems, the thermodynami limit ondition does not always hold, and more subtle single
sample analysis alsoin the typi al ase have to betaken into onsideration[30℄.
1.2.5 Repli as
The al ulations are arried out via a\subtle tri k": itmu h easier to ompute
hlogZi= lim n!0 Z n 1 n (1.15)
The last equation is an identity for ontinuous n, but the tri k onsists in al ulating rst
Z n
for integer n, taking the 0 limit is a se ond time. The repli ated partition fun tion, after
averagingoverthe samedisorder realizationbe omesapartitionfun tionof n systems,without
disorder, but with ane e tive attra tive intera tion between the various repli as. The reason
for this attra tion is intuitively quite simple [79℄: be ause they share the same Hamiltonian
with basi ally a singlelarge deepest valley,then the repli aswillall fallin that, and the order
parameter willbea numberq whi hwillmeasure the average distan e between repli aswithin
this single valley. But in a systems with several metastable states, the situation an be more
ompli ated, with some repli as trapped in a valley and some inanother. This e e t is alled
repli a symmetry breaking (RSB).Te hni ally it appears as a standard spontaneous breaking
of a symmetry, the permutation symmetry S
n
of the n repli as. The problem is that this
symmetry is broken only when one onsiders some number of repli as whi h is non-integer
and in fa t smaller than one. Even though this point has been elegantly solved by Parisi [2℄,
the validity of taking the n ! 0 limitstill la ks a general rigorous justi ation ([60℄, [59℄ and
referen es therein). The last hapter will try to deal with this problem in an indire t way.
We will not show (unfortunately) that the physi al quantities de ned on the n ! 0 ve tor
spa es are well de ned mathemati al obje ts, but at least that, onthe lass of systems we are
interested in, the e e tive repli a Hamiltonian an lead to rigorous variationalresults. In the
ase of fully onne ted models,the repli amean eldtheory an bestated interms of asingle
s alarnn matrix,whoseelementsare theoverlaps hosenviaadeterminates hemeand that
play the role of orderparameters. In the ase ofdiluted systems,however, it emerges the need
for the determinationof a full distributionof multi-spinoverlaps [1,9℄ that an be ompletely
hara terized via the introdu tion of a lass of fun tional order parameters[8, 9,12℄
(~)
that essentially enumerate the fra tion of repli ated spins in a parti ular repli a state, as it
will be ome lear in the ourse of the al ulations
8
. These fun tional order parameters have
stillamean eldnatureand willbeexpressed interms of seriesof multi-spinoverlapfun tions
averagedoverthemeanlo al eldsdistributionsseenbyanaveragevertex inaparti ularstate.
The free-energy of the system an be writtenas a fun tion of (~), and will thereforebea
fun tional of the lo al elds probability distributions, averaged over all possible states of the
system. In the N ! 1 limit
9
, the dominant ontribution to the partition fun tion is found
extremizing the freeenergy with respe t to the fun tionalorder parameter
One isleft with a set of self onsistent integral equationsfor the e e tive elds probability
distributions,that an besolved analyti allyornumeri ally(dependingonthe ases). Insome
spe ial ases, namely on the T = 0 line for some lasses of models, these equations further
simplifydue to the ollapsingofthe fun tionalform ofthe probabilitydistributions intoseries
of weighted deltafun tions. Whenthis happens, oneis leftwith aset ofalgebrai equations in
the weightsthatoftenadmitanalyti solutionsina losedform. This isparti ularlyinteresting
in the eld of ombinatorial optimization, thanks to the existing general mapping pro edure
between the solutionsof the random ombinatorial problemand the zero temperatureground
states of the asso iated spin model. Moreover, the assignments of the problem variables with
a given (typi ally low) number of violated onstraints orrespond to metastable lo alground
states with positive energy. The logarithm of the number N(e) of su h metastable states is
a fun tion of the their energy density e = E=N and is known as Con gurational Entropy or
Complexity[7℄ : (e)= 1 N log[N(e)℄ (1.16) 8
Thereareatleasttwowaystode netheorderparameter,dependingonwhetheronefo uses onthewhole
graphsoronsomepartofit. Seeappendi esC,C.1andC.2 forsomedetails.
Therefore, the measure of the extensivity of the Complexity willbeanimportantindire tway
to study the hardness of the random ombinatorial problemdepending on the position in the
phasespa eoftheasso iatedpinmodel,andwillstressthedeep onne tionbetween thetheory
of the glassy transitions in disordered systems and the on epts of omputational omplexity
in theoreti al omputer s ien e.
Aswe just said, the ingredientsof frustrationand/or disordertypi ally indu ethe onset of
transitions from a uniform paramagneti to one or more kind of glassy phases in the ontrol
parameters 10
spa e ofthe model.
1.2.6 Cavity
Thesamesolutionsandthesamephysi alinsights anberea hedviathe avitymethod. Cavity
was invented in1986 forthe solutionof theSK model[2℄, but wasre ently reformulatedinthe
diluted systems framework [23℄ and related to an algorithmi understanding of the pro ess in
the aseofitsdire tzerotemperatureformulationin[24,30,29℄. Thebasi ideaof themethod
applied tospin models on dilutedhyper-graphs is the following:
Assume that, likeinthe repli amethod,due tothelo altree-likestru ture of the
hyper-graphandthemean eldnatureofthemodel,spinvariablesbe omeun orrelatedatlarge
distan es if the system is in a single state. The in uen e of the graph on a single spin
an betherefore easilywritten interms of un orrelated lo ale e tive elds a tingon it.
Startingwith asystem ofN variables,addnow avariableS
0
ofdegreek (on average one
will add a fra tion of spins
k
) and onne t it to the rest of the hyper-graph in order to
ompletek lausesoffun tionnodesofthe N verti esgraphswithvariablesfS
1 a ;:::;S k a g a ,
where a is the rank index, i.e. it indexes all the variables other than S
0
belonging to a
given lause (or energy onstraint, asequivalently indi ated throughoutthis thesis).
AssumethatfS 1 a ;:::;S k a g a
wherepreviouslydis onne tedwithprobabilityone inthe
ther-modynami limit(no short loops) and therefore un orrelated:
P (N) (fS 1 a ;:::;S k a g a )'P (N) 1 (fS 1 a g a ):::P (N) k (fS k a g a )' Y a P (N) 1;a (S 1 a ):::P (N) k;a (S k a ) (1.17)
Then it ispossible to ompute the new P
(N+1) (S 0 ;fS a 1 ;:::;S a k g a
) via Bayes theorem as:
P (N+1) (S 0 ;fS 1 a ;:::;S k a g a )' k Y =1 P (N) (fS a g a )e (0) (S 0 ;fS a g a ) ' k Y =1 Y a P (N) ;a (S a )e (0) (S 0 ;fS a g a ) (1.18) where (0) (S 0 ;fS a g a
) is the lo alenergy onstraint
of eq. (1.7) where the dependen e
on the -th lause spin variables has been made expli it, as well as the referen e spin
index 0. Integrating overthe variablesfS
1 a ;:::;S k a g a
one nally obtains:
P (N+1) (S 0 )' k Y =1 Y a X S a =1 P (N) ;a (S a )e (0) (S 0 ;fS a g a ) : (1.19) 10
Were all that therelevant ontrolparametersare in thesemodelsthetemperatureT,the graphdilution
This last equation de nes an iterative method to al ulate P (N+1) 0 (S 0 ) from fP (N) ;a (S a )g ;a .
Thankstothe rstassumption,theequationsforP
(N) j (S j )andP (N+1) (S 0
) anbeeasilywritten
as P (N) j (S j ) = e hjSj 2 osh( h j ) P (N+1) 0 (S 0 ) = e h 0 S 0 2 osh( h 0 ) (1.20)
Writing self onsistent equations for the avity elds is then possible inserting (1.20) in(1.19)
and iterating. In the typi al ase, one an then average over all spins, getting an expression
for the distribution P(h)weighted over the degree and rank distribution of the typi al
hyper-graphs.
In fa t, this assumption is globally valid only if the system is in a single pure state. In
many states =1;:::;N
states
are present,the previousequations are validwithin agiven state
, i.e. a luster of solution separated by other lusters. Equations (1.20) will then be state
dependentand theself onsistent ondition(1.19)willhavetobeaveragedbothoverthe sitesi
andover thestates . Thispi ture orrespondstothe one step repli asymmetry breakingone
and is frequent in disordered spin systems. The avity method formulated in this way works
essentially by indu tion and assumes no non trivial orrelations within lusters or inside the
same lusterthat ouldoriginfromthegeometryofthegraph,eventhoughtrivial orrelationsof
a hierar hi al nature an be taken into a ount
11
. The disregarding of orrelations is ommon
with the repli a approa h, as it should be if we laim the two to be equivalent, and it is a
limitationof thetheory thatwillhavetobeover omeinthenearfuture ifone wantstobeable
to systemati allyatta k problems with more omplex geometri alstru ture.
During the avity iterationpro ess, one is bound tomake asmallerrorof order 1=N, sin e
the ensemble of random graphs one is working with hanges slightly under the N ! N +1
avityiterations. Thiserror anbehealedviaa leverbalan ingofverti esandedgesadditions
and erasures. More in detail:
A hyper-graph H
N;M
withN verti es and M edges isdrawn from the desired ensemble.
A avity is arved in it, where q verti es are left with degree equal to minus one their
initialone, through a proper erasure of surrounding verti es and edges. q is hosen as a
fun tion of the degree of the erased verti es and the rankof the erased edges
12 .
Lo al avity magneti elds h
i
a ting on the avity spins S
i
are supposed to follow an
initially unknown probability distribution P
i (h
i
), in prin iple di erent from site to site
and with eld values dependent on the state of the system.
Undertheadditionofanew avityspinS
j
ofdegreek
j
onne tedwithsomeoftheprevious
avitysitesthroughgivennumberofhyper-edgesofsuitably hosenranks,theprobability
distributionsof thenew avity elds are al ulated inaself onsistentiterativeway. The
11
Trivial orrelations are takenin prin ipleinto a ountvia further lusterization stepsthe same\ lusters
within lusters"hierar hyimpliedbytheRSBParisi's onstru tion.
12
iteration isbuilt in order toself onsistently stabilize the avity elds distributions on e
the original hyper-graph isretrieved
13 .
The pro edure is repeated adding and deleting edges and verti es in a balan ed way, in
order toretrieve the hyper-graph belonging tothe desired startingensemble.
Energy shifts are al ulated under the iteration, allowing to al ulate the free energy,
the energy density and other physi al quantities (for example the omplexity) in the
thermodynami limit.
Averages overthe hyper-graphs ensembleand the model ouplings are performed.
If applied to single spins, the avity method is mean eld in nature. In order to possibly
e e tivelyextenditto nitedimensionalmodelsorwithlatti eswithsomenontrivialgeometry
one would need to onsider the in uen e onthe iteration ofmore omplex groupsof variables.
Thishasbeenpartiallydonewiththe lustervariationmethod(CVM)forferromagneti models,
but the extensionin presen e of frustration isstillan open issue.
1.2.7 Phase spa e stru ture
twopossible s enarios have been en ountered inthe models studied:
ARepli aSymmetri phase (RS):generi ally,thedistan eonthelatti ebetweentwo
spins is large, at least of the order of random loops forming in the topology, i.e. of the
order O(logN). It is thereforereasonable to assume that the spins remain un orrelated.
In the avitylanguagethis meansthat theGlobal Ground State(GGS)energy ofagraph
with a referen e avity of q spins arved in it an be written as an additive fun tion of
the valuesofthe avityspins S
i=1;:::;q
,weightedbythe lo al elds h
i=1;:::;q
a tingonthem.
When onsidering the ensemble of random avity graphs, the lo al elds turn out to be
i.i.d. random variables, and their distribution is denoted with P(h). The lo al eld will
therefore not u tuate from state to state be ause of the presen e on only one GGS a,
and the distribution P(h)will be anaverage overall sites. In the repli a formalism, the
sameP(h)willbetheone determiningthemulti-spinoverlaps ontainedinthe fun tional
order parameter (~).
A One Step Repli a Symmetry Broken phase (1RSB): The phase spa e splits in
an exponential number of metastable Lo al Ground States (LGS), de ned as states in
whi h the energy annot be lowered by ipping a nite number of spins. In presen e of
several groundstates,the assumptionisthatthereisaone-to-one orresponden eamong
the LGS before and after the addition of spins or edges (at least for the LGS with low
energies). Equivalently we assume that the perturbation due to the hange of the value
of a avity spin propagates (in the limit N going to in nity) only to an in nitesimal
fra tion of the latti e. Therefore it is possible to write an iteration pro edure for the
wholepopulationofLGSwithgiven energy. Howeveritmaywellbethattheorderof the
LGSenergies hange duringthe graphoperations,and the GGS afteriterationisnot the
same LGS as the one before. The problem is to take into a ount these level rossings,
whi his not donein the RSsolution andturns out tobeautomati ally done inthe RSB
13
Figure 1.4: Pi torialview of the energy lands apein the phase spa e of asystem inthe 1RSB
phase. The energy is on the verti al axis. utting the pi ture at de nite values of the energy
one nds lustersof solutions in reasingin number and dimension.
e
e
d
e
c
e = 0
γ
γ
<
d
γ
<
γ
c
e = 0
e
e = 0
e
e
d
γ
γ
>
c
d ~ O(N)
out
d ~ o(N)
in
Figure1.5: 1RSB lustering in phasespa e.
solutions via the repli a formalism. One is then for ed to follow a large population of
the LGSof lowest energy,large enough sothat one an be sure toobtain the GGS when
iterating.
In g.(1.4)weshowapi torialviewofthe energy lustersinthe1RSBphase. Typi al xed
energysli esofthispi tureshowhow,in reasingtheenergy,di erent lustersaresele ted. This
is shown is g. (1.5). This qualitative pi ture as been extensively studied for p > 2-spin and
K >2-SAT modelsin re ent years [11, 21,53℄,mainlywith variationalte hniques. This is the
intuitiveidea we'llhave inmind inthe rest ofthis work. In some lu ky ases- and indeed the
p-spin model will be one of them - this pi ture will turn out to have an exa t interpretation.
In some others, as for instan e the random 3-SAT, no rigorous proof is present. However
this pi ture is highly probable to be orre t and what is more important it turned out to be
extremely useful inthe development of a new lass of algorithmof potentialvast use. Indeed
very re ently [30, 29℄ exa t solutions of the p-spin modeland the K-SAT at zero temperature
in a ertainrange of thephase spa e parametershave been a hieved under this assumption on
the form of the energy levelsdistribution.
the ase of the Viana-Bray model on diluted graphs [23, 24℄. In this models typi ally slow
de ayinglong range orrelationsare present. However, froma omputationalpointof viewthe
Viana-Bray models turns out to be easy in the phase spa e regions of interest. Indeed, it is
also due to the presen e of this long range orrelations that Viana-Bray like models turn out
tobe omputationallysimple,be ausethe solutionspa e willingeneralbe onne tedby paths
allowingthe rea hingofany phasespa epointwitha leverbutsub-extensivesequen e of lo al
adjustments.
The main al ulation steps reviewed in the last paragraphs are then the ones indi ated in
s hema (1.6), where the onne tionto the eld of ombinatorialoptimizationis made evident.
Finally, some di eren es between the repli a and the avity methods are listed in the
fol-lowing:
While repli as for e the introdu tion of an order parameter that has already undergone
average over the quen hed disorder, the avity equations an also be written ona single
sample(hyper-graph). This makesthe avity approa hmoreapttobeappliedtospe i
real world problems.
The avity approa h deals with well de ned mathemati al quantities and is manifestly
variational,while thewellde nitenessof the repli amethod (namelyinthe RSB ase)is
stillun lear.
On the other hand,the repli a methodis mu hmore elegantand ompa t (espe ially at
nite temperature), itdoesnot requirefurtherpostulatesandassumptionsonthe energy
level distribution, that in prin iple depend on the model onsidered, and its equations
an behandled infull generality.
Wewilldevelopthe repli amethod,o asionallytaking advantage ofphysi alinsights
om-ing from the avity pi ture. A throughout treatment on the state of the artof the avity
Model Hamiltonian H
couplings configuration {J}
Fixed hyper−graph H(V,E) and
Partition Function Z
Replication
Z n
Z
<
n
>
n −> 0 limit
Functional Order parameter
ρ(σ)
Local Fields Distributions
i
Proper Definition of
the Cavity Hyper−Graph
Depending on Ensemble
Single Sample Free−Energy
Single Sample Properties
Solution Search Algorithms
...
Disorder Average
Disorder Average
Hypothesis on LGS Energy
Distribution
Cavity Calculation
Stationary Condition on the Potential
Ν −> ο
o limit
on Single Samples P (h )
i
Single Sample Phase Space
Iterative Equations for
Replica Calculation
Phase Transitions
Physical Observables
Prediction on Average Behavior
of Algorithms
...
Search on Complex Structures
Cost Functions
Combinatorial Optimization
Computer Science
Disordered Systems Physics
Energy Shifts
Comlexity
P(h) of Local Effective Fields
In terms of Average Probability Distributions
Self Consistent Equation for
ρ(σ)
< F >, Average Complexity
Computational Complexity
Figure 1.6: General al ulation strategy via repli a and avity methods and onne tion to
The generalized diluted p-spin model
Wearenowgoingtodevelopindetailstheanalyti alrepli ate hniquespreviouslydes ribed. In
doingsowewill hoose aspe i lassofmodelsofgeneralimportan e,namelyageneralization
of the p-spin model on un orrelated random hyper-graphs with arbitrary degree and rank
distribution.
Ifwede ne
k
asthefra tionofspinvariableswithdegreekandv
l
thefra tionofintera tions
of rank l, the resulting mixed hyper-graph stru ture will be hara terized by the following
distributions: Q( ^ l) = X l v l Æ( ^ l l) (2.1) P( ^ k) = X k k Æ( ^ k k) (2.2) <l > = X l lv l (2.3) <k > = X l k k (2.4)
We noti ethat we ould introdu e two generating fun tions
v(x) = X l v l x l (2.5) (x) = X k k x k (2.6) (2.7)
where (2.6) is the same of [69℄, but the (2.5) generalizes it to more omplex stru tures su h
as the mixed rank hyper-graphs we work with. The generating fun tion formalism is not
stri tly ne essary, but an be very helpful when one is interested in omputing more omplex
topologi al properties of the hyper-graph and indeed will be expli itly used in some ases. In
the generalizedp-spin modelthe Hamiltoniantherefore reads
H = M X l H l (2.8) H l = X i1<:::<i l J i1;:::;i l s i1 ;:::;s i l (2.9) with M = <k > <l > N (2.10)
and P(fJ i 1 ;:::;i l g l ) = Y l Y i 1 <:::<i l ((1 l! l N l 1 )Æ(J i 1 ;:::;i l )+ l! l N l 1 Æ(J i 1 ;:::;i l 1)) (2.11) P(fJ i 1 ;:::;i l g l ) = Y l Y i 1 <:::<i l ((1 l! l N l 1 )Æ(J i 1 ;:::;i l )+ (2.12) l! l 2N l 1 (Æ(J i 1 ;:::;i l 1)+Æ(J i 1 ;:::;i l +1))
respe tively for the ferromagneti and for the frustrated ase,and
l
=(<k >=<l >)v
l .
2.1 Combinatorial optimization interpretation of p-spin
models: the XOR-SAT
Wenoti ethattheseHamiltonians anbealsoseenasthe ostfun tionofa lassa ombinatorial
optimizationproblemsknown underthe nameofXOR-SAT([19,21,82℄,alsoextended in[25℄).
The XOR-SAT problem is not NP, but it is nevertheless a very useful prototype treatable
optimization problem in order to test the power of statisti al physi s tools. Beside this, its
diluted p-spin version bears many interesting properties from the point of view of stru tural
glasses and granular physi s [79, 20, 15, 80, 81℄, so its study is interesting for a transversal
number of dis iplines. We show the ase of the K-XOR-SAT model with K variables per
onstraint,whi h anbeviewedasaperfe tlybalan edversionoftherandomK-SATproblem
1 .
GivenasetofN Booleanvariablesfx
i
=0;1g
i=1;:::;N
,we onstru taninstan e ofK-XOR-SAT
as follows: given original K-SAT lauses (x
i 1 _x i 2 _x i k ) or (x i 1 _x i 2 _x i k ), every sub- lause
ontainedinone ofthem must appear dire ted andnegated inthe orrespondingK-XOR-SAT
onstraint an even number of times. In the K = 2 ase we'll therefore de ne the following
elementary onstraints(2- lauses sets with 50% satisfyingassignments)
C(ijj+1) = (x i _x j )^(x i _x j ) C(ijj 1) = (x i _x j )^(x i _x j ) ; (2.13)
In the K =3 ase we'll have onstraints(4- lauses sets with 50% satisfyingassignments)
C(ijkj+1) = (x i _x j _x k )^(x i _x j _x k ) ^ (x i _x j _x k )^(x i _x j _x k ) C(ijkj 1) = (x i _x j _x k )^(x i _x j _x k ) ^ (x i _x j _x k )^(x i _x j _x k ) ; (2.14)
in the K =4 ase we'llhave 8- lauses of type
C(ijklj+1) = (x i _x j _x k _x l )^(x i _x j _x k _x l ) ^ (x i _x j _x k _x l )^(x i _x j _x k _x l ) ^ (x i _x j _x k _x l )^(x i _x j _x k _x l ) ^ (x i _x j _x k _x l )^(x i _x j _x k _x l ) 1
C(ijklj 1) = (x i _x j _x k _x l )^(x i _x j _x k _x l ) ^ (x i _x j _x k _x l )^(x i _x j _x k _x l ) ^ (x i _x j _x k _x l )^(x i _x j _x k _x l ) ^ (x i _x j _x k _x l )^(x i _x j _x k _x l ) (2.15)
and so on. Here ^ and _ stand for the logi al AND and OR operations respe tively and
the over-bar is the logi al negation. Let's on entrate on the K = 3 ase, that ontains all
general elements. In the next hapter we will study a mixed version of this modelin the ase
of a mixture of 2 and 4 lauses, whi h we will all 2+p-XOR-SATas it shares many ommon
features to the 2+p-SAT model studied in [11℄. By randomly hoosing
2
a set E of M triples
fi;j;kg among the N possible indi es and M asso iated unbiased and independent random
variablesJ
ijk
=1,we onstru t a Boolean expression inConjun tive NormalForm (CNF)as
F = ^ fi;j;kg2E C(ijkjJ ijk ) : (2.16)
A logi alassignmentofthe fx
i
g'ssatisfyingall lauses,that isevaluatingF totrue, is alleda
solution of the XOR-SATproblem. If nosu h assignmentexists, F issaid tobeunsatis able.
A slightlydi erent hoi eof J
ijk
allowsto onstru t XOR-SATformulwhi hare randombut
guaranteed to be satis able. This will lead to the ferromagneti spin ase: to every Boolean
variablewe asso iate independently drawn randomvariables "
i =1, and de ne J ijk =" i " j " k
forallfi;j;kg2E. Forthis hoi e,CNFformulaineq.(2.16)issatis edbyfx
i jx i =+1if "= +1; x i
= 0 if " = 1g. As we shall dis uss in great detail, these formul provide a uniform
ensembleof hard satis able instan es for lo alsear h methods. We referto this version of the
modelasthesatis ablehSAT.Indeed,therandomsignsofJ
ijk
anberemovedinthissatis able
ase by negating all Boolean variables x
i
asso iated to negative "
i
. The resulting model has
J ijk
= +1 for all fi;j;kg 2 E, and the for ed satisfying solution is x
i
= 1; 8i = 1;:::;N.
The use of the f"
i
g is a way of hiding the latter solution by a random gauge transformation
without hanging the properties of the model. The impossibility of inverting eÆ iently the
gauge transformation by lo al methodsis a onsequen e of the bran hing pro ess arising form
the presen e of K =3variables inea h onstraint. Forany K >3 the same result would hold
whereas for K =2the problemtrivializes. The XOR-SAT model an be easily des ribed asa
minimization problem of a ost-energy fun tion over a random hyper-graph. Given a random
hyper-graph G
N;M
=(V;E),whereV isthe set ofN verti esandE isthe setof M hyper-edges
joiningtriples of verti es,the energy fun tionto be minimizedreads
H J [S℄=M X fi;j;kg2E J ijk S i S j S k ; (2.17)
where ea hvertex i bears a binary \spin" variableS
i
=1,and the weights J
ijk
asso iated to
the randombonds anbe either1atrandom,intheso alled frustrated ase, orsimplyequal
to 1 in the unfrustrated model. We see that this is indeed the parti ular ase of the 3-spin of
eq.(2.9). On ethe mappingS
i =1if x i =1and S i = 1if x i
=0isestablished, one an easily
noti ethat theenergyfun tionineq.(2.17)simply ountsthenumberofviolated lausesinthe
previously de ned CNFformul withthe sameset of J's. The frustratedandthe unfrustrated
ases orrespond tothe XOR-SAT and tothe satis able XOR-SAT formul respe tively.
2
2.2 From the partition fun tion to the average free-energy
The onstraints onthe degreedistributionwillhave tobeintrodu edalongthe omputationof
the logarithm of the partitionfun tion.
Z =e M X si e P k H k (2.18)
Following the approa h of ref. [19℄, we ompute the free energy of the model with the repli a
method,exploitingthe identitylog<Z
n >=1+n<logZ >+O(n 2 ). The n th momentof the
partition fun tion isobtained by repli ating n times the sum over the spin on gurations and
then averagingoverthe quen hed disorderTheaveragedn-th momentofthe partitionfun tion
takes therefore the followingform,a part from anormalization fa tor:
<Z n >=e n M X ~ s i <e P n a=1 P l P i 1 ;:::;i l Ji 1 ;:::;i l s a i 1 :::s a i l > (2.19)
where the average value of anobservable is given by:
<> = [P(k)℄ Z Y i 1 <:::<i l P(J i 1 ;:::;i l )() N Y i=1 Æ( X l X i 1 <:::<i l jsign(J i 1 ;:::;i l )j k i ) (2.20) Y l Æ(Mv l X i 1 <:::<i l jsign(J i 1 ;:::;i l )j) (2.21)
[P(k)℄ is a normalization fa tor ne essary to res ale to one the sum over the onstrained
probability distribution of the ouplings:
[P(k)℄ Z Y i 1 <:::<i l P(J i1;:::;i l ) N Y i=1 Æ( X l X i 1 <:::<i l jsign(J i1;:::;i l )j k i ) Y l Æ(Mv l X i 1 <:::<i l jsign(J i1;:::;i l )j) (2.22)
The two inserted delta fun tions are there toensure the onstraints on degreeand intera tion
terms distribution. In fa t,the onstraint overthe fra tion of xed rank plaquettes is already
taken into a ount in the parti ular form of the distribution, therefore the normalization an
be limited tothe term
[P(k)℄ Z Y i 1 <:::<i l P(J i 1 ;:::;i l ) N Y i=1 Æ( X l X i 1 <:::<i l jsign(J i 1 ;:::;i l )j k i ) (2.23)
Its value is al ulated in the appendix inthis ase. The nal value in the large N limitis:
[P(k)℄e N <k> P k k log <k > k k ! (2.24)
Even more in generality,H
l
ould be inthe form
H l = X i 1 <:::<i l J i 1 ;:::;i l G (l ) [~s℄ (2.25)
where thefun tions G
(l )
depend onthe parti ularmodelunder onsideration. In this work,for
instan e,we onsiderotherrelevantexamplessu hastheBi oloringproblemofarandomrank3
hyper-graph, whereonlyG
(3) = (s i1 s i2 +s i1 s i3 +s i2 s i3
model, where G (3) = Q 3 l =1 Æ(s i l
; 1) and the oupling variables follow a di erent probability
distribution too. Going ba k to our generalized p-spin modelwe an write the delta fun tions
in their integral form
Y l Æ(M l X i 1 <:::<i l J i 1 ;:::;i l )= Z Y l ( d l 2 )exp( iM X l l v l )exp(i X l l X i 1 <:::<i l jsign(J i 1 ;:::;i l )j) (2.26) Y i Æ( X l X <i 2 ;:::;i l > i jsign(J i 1 ;:::;i l )j k i )= Z Y i ( d i 2 )exp( i X i i k i )exp(i X i 1 <:::<i l ( k X j=1 i j )jsign(J i 1 ;:::;i l )j) (2.27)
Infa t,aswesaid,the hoi ewehavemadeontheprobabilitydistributionofthe ouplings(and
the onsequent value of the quantities
k
) already impliesthe rst onstraint tobe satis edin
the large N limit. Indeed, if we expli itlyinsert the rst delta fun tion(also the normalization
fa tor willa ordingly hange),we areleft withone supplementaryseries ofsaddlepoint
equa-tions inthe variables
l
. Insertingthe solutionsforthelattervariablesintothe ommonsaddle
point equations, we retrieve equivalent expressions. The averaged n-th power of the partition
fun tion be omes, inthe ase of the dilutedferromagnet,
<Z n > exp ( nM) X ~ s i Z Y i ( d i 2 )exp i N X i=1 i k i ! exp 0 <k > <l > N + X l v l N l 1 exp 0 X i1;:::;i l X a s a i 1 :::s a i l +i l X j=1 ij 1 A 1 A (2.28)
We ould now go on in the al ulation treading a path similar to the one followed for the
fully onne ted models, tra ing out the repli ated spin variables through the introdu tion of
a whole series of overlap and multi-overlap quantities. Due to the distribution of ranks and
degrees, however, the numberofoverlapfun tionthatwewouldneedtotakeinto onsideration
is in nite, and we are better o if we exploit a more ompa t mathemati al notation via a
generating fun tion formalism of the overlap series
3
. The orre tgenerating fun tion for this
kindofproblemsturnsouttobewritableasafun tionalorderparameterinthe form[19,9,12℄
(~)= 1 N X i Æ(~ ~s i )e i i : (2.29)
In the ase of Poissonian hyper-graphs, due to the self similarity property of eq. (1.5) that
substituted inteq. (1.6) leads to q
poiss k = poiss k , the elds i
are redundant and re-absorbed in
the degree distribution (Poissonian degree hyper-graphs are the ones obtained in the
thermo-dynami limitwhen using the \free" ouplings probability distributions (2.11) and (2.12)). In
this asethe quantity (2.29)dire tlyrepresentsthe fra tionofrepli atedspins s
a
i
intherepli a
state
a
in the whole graph as well as in the avity one. However, in the general ase it is
ne essary to add a eld
i
that an be physi ally interpreted in the following way: e
i i
is an
3
