P
RAMANA °c Indian Academy of Sciences Vol. 64, No. 6—journal of June 2005
physics pp. 1161–1173
Statistical physics, optimization and source coding
RICCARDO ZECCHINA
International Centre for Theoretical Physics, Strada Costiera 11, I-34100 Trieste, Italy E-mail: zecchina@ictp.trieste.it
Abstract. The combinatorial problem of satisfying a given set of constraints that depend on N discrete variables is a fundamental one in optimization and coding theory. Even for instances of randomly generated problems, the question “does there exist an assignment to the variables that satisfies all constraints?” may become extraordinarily difficult to solve in some range of parameters where a glass phase sets in. We shall provide a brief review of the recent advances in the statistical mechanics approach to these satisfiability problems and show how the analytic results have helped to design a new class of message-passing algorithms – the survey propagation (SP) algorithms – that can efficiently solve some combinatorial problems considered intractable. As an application, we discuss how the packing properties of clusters of solutions in randomly generated satisfiability problems can be exploited in the design of simple lossy data compression algorithms.
Keywords. Disordered systems; random combinatorial problems; survey propagation.
PACS Nos 02.50.-r; 75.10.Nr+c; 05.20.-y; 89.70.+c
0. Introduction
Some recent advances in statistical physics of disordered systems have provided in- teresting results also for computer science (optimization), information theory (error correcting codes) and discrete mathematics (random structures). On the dynamical side there has been a lot of interest in the study of approximate static measures characterizing the out-of-equilibrium phase of algorithmic and physical stochas- tic processes. On the static level, the study of the geometrical properties of the ground states of spin-glass-like energy functions has provided new insights for un- derstanding the onset of computational complexity in many random combinatorial optimization problems [1,2] as well as in decoding problems [3,4]. New algorithms have appeared which are based on statistical-physics analytical methods. The scope of this paper is to give a brief review of such studies.
In computer science the field of combinatorial optimization [5] deals with the issue of classifying the computational difficulty (‘hardness’) of discrete minimization problems and of analysing/designing search algorithms. As in statistical physics models, a generic combinatorial optimization problem is composed of many discrete variables – e.g., Boolean variables, finite sets of colors or Ising spins – which interact
1161
through constraints typically involving a small number of variables, that in turn sum up to give the global energy function.
When the problem instances are extracted at random from nontrivial ensembles, computer science and statistical physics meet: many models considered to be of basic interest for computer science are nothing but spin glasses defined over finite connectivity random graphs, i.e. diluted spin glasses [1,6]. Their associated energy function counts the number of violated constraints in the combinatorial problem.
Explaining the onset of hardness in such problems is a central issue for computer science as well as for understanding the very low temperature (T = 0) phase of disordered systems.
Surprisingly enough, there already exist concrete engineering applications: For instance, among the most effective error correcting codes and data compression methods are the low density parity check algorithms [3,7,8], which indeed implement an energy minimization of a spin glass energy defined over a sparse random graph.
In such problems, the choice of the graph ensemble is a part of the designing techniques, a fact that makes spin glass theory directly applicable.
The applicability of the average case results, however, is not so straightforward in the general case for combinatorial problems: in many concrete situations the probabilistic set-up is not defined and, consequently, the notion of a typical case analysis does not play any obvious role. The study of the connection (if any) between worst-case and typical-case complexity is indeed an open one and very few general results are known [9]. Still, a precise understanding of instances of non-trivial random problems promises to be important under many aspects. New algorithmic results as well as many mathematical issues have been put forward by the statistical physics studies, with examples ranging from phase transitions [2,10]
and out-of-equilibrium analysis of randomized algorithms [11] to new classes of message-passing algorithms [12,13].
The physical scenario for hard combinatorial problems predicts the existence of a dynamical transition leading to a trapping of local search processes in metastable states (for exponentially long times). Depending on the models and on the details of the process – e.g., cooling rate for SA – the long time dynamics is dominated by different types of metastable states at different temperatures. A common feature is that at zero temperature and for simulation times which are sub-exponential in the size of the problem there exists an extensive gap in energy which separates the blocking states from true ground states. Such a behavior can be tested on concrete random instances which therefore constitute a computational benchmark for more general algorithms.
Of particular interest for computer science are randomized search processes which do not properly satisfy detailed balance and that are known (numerically) to be more efficient than SA-like algorithms in the search for ground states [14]. Whether the physical blocking scenario applies also to these artificial processes, which are not necessarily characterized by a proper Boltzmann distribution at long times, is a difficult open problem. The available numerical results and some approximate analytical calculations [11,15] seem to support the existence of a thermodynamical gap, a fact which is of utmost importance for optimization. For this reason (and independently from physics), during the last decade the problem of finding minimal energy configurations of random combinatorial problems similar to diluted spin
glasses – e.g., random K-satisfiability (K-SAT) or graph coloring – has become a very popular algorithmic benchmark in computer science [6].
In the last few years there has been so much progress in the study of spin glasses over random graphs which has shed new light on mean-field theory [16] and has produced new algorithmic tools for the study of low-energy states in large single problem instances [12]. Quite surprisingly, problems which were considered to be algorithmically hard for local search algorithms, like for instance random K-SAT close to a phase boundary, turned out to be efficiently solved by the survey propa- gation (SP) algorithm [2,12] arising from the replica symmetry broken (RSB) cavity approach to diluted spin glasses. Such types of results call for a rigorous theory for the functioning of SP and bring new mathematical challenges of tremendous potential impact. It has been experimentally shown that often the hardest ran- dom instances to solve tend to be concentrated in a narrow region around some critical threshold (like the transition between the satisfiable and the unsatisfiable region in the case of Boolean satisfiability [6,17]). This phenomenon can be physi- cally explained by considering that close to the phase transition point the solution space breaks up into many smaller clusters [12]. Solutions in separate clusters are generally far apart. Moreover, finite energy clusters that correspond to partial solutions – which satisfy some but not all of the constraints – are exponentially more numerous than the clusters of complete solutions and act as dynamical traps for local search algorithms like simulated annealing or even more specialized heuris- tics. SP turns out to be able to deal efficiently with the proliferation of such clusters of metastable states.
The SP algorithm consists of a message-passing technique which is closely related to the better known belief propagation (BP) algorithm [18] – recently applied with great success in the decoding of error-correcting codes based on sparse graph encod- ings – but which differs from it in one crucial point. The messages sent along the edges of the graph underlying the combinatorial problem describe in a probabilis- tic way the cluster-to-cluster fluctuations of the optimal assignment for a variable;
while BP performs a ‘white’ average over all the solutions, SP tells us which is the probability of picking up a cluster at random and finding a given variable forced to take a specific value within it (‘frozen’ variable). Once the iterative equations have reached a fixed point of such probability distributions (called ‘surveys’ because they capture somehow the distribution of the ‘beliefs’ in different clusters), it becomes possible in general to identify the variables which can be safely fixed and to simplify the problem accordingly [13].
Moving now to the experimental point of view, the SP-inspired decimation al- gorithm has been efficiently used to solve many instances in the hard region of different satisfiability problems and of the graph coloring problem, including in- stances too large for any earlier method [12]. For example, for random 3-SAT, instances close to the threshold, up to sizes of order 107 variables were solved and the computational time in this regime was found experimentally to scale roughly asNlnN. The finite-energy version of the SP-inspired decimation, although more demanding from the computational time viewpoint, was successfully employed for optimizing the assignments of large unsatisfiable 3-SAT instances [19].
In what follows, we shall present a short review of the SP theory together with some recent results concerning a generalization of the SP algorithm which allows
us to address selectively the different clusters of ground states, thereby providing algorithmic evidence for a clustering phase in hard combinatorial problems. The computational perspective of such a device looks promising: indeed the possibility of addressing and retrieving a large number of specific ground states allows us to develop a very simple lossy data compression scheme, making use of message pass- ing techniques both in the coding and decoding stages and exploiting the natural clustered structure of ground states for data quantization purposes.
1. Phase diagram
We shall consider the random K-SAT problem as an archetypical case. However, similar results have been found or are expected to hold for many other types of random combinatorial problems, e.g. graph coloring.
K-SAT is a combinatorial problem (forK >2) which plays a key role in theoreti- cal computer science, having been the first problem to be proven to be NP-complete.
It can easily be stated: Given N Boolean variables andM constraints taking the form of the OR function ofKvariables, either directed or negated,K-SAT decides whether there exists or not a global truth value assignment that does not violate any constraint. The same variable may appear directed or negated in different clauses giving rise eventually to frustration.
The random version ofK-SAT, in which for each clause the variables are chosen uniformly at random (with no repetitions) and negated with probability 1/2, has been extensively studied in the last years. Taking the ratio of the number of clauses to the number of variables, α = M/N, as control parameter it turns out that a phase transition takes place in the thermodynamical limit at a finite valueαc(K).
For α < αc(K) the problem is generally satisfiable (SAT) and forα > αc(K) the problem is, on the other hand, not satisfiable (UNSAT).
This phase transition has been seen numerically [17] and, as mentioned in the introduction, extensive experiments [6] have shown that the algorithmically hard instances are typically characterized byαclose toαc. On the analytical side, the existence of the threshold phenomenon for largeN [20] has been proved rigorously.
Upper and lower bounds onαchave been found as well, using statistical or ‘physical’
methods [21–24].
The cavity method of statistical physics has been applied to K-SAT [2,12] pro- viding an accurate analytical computation of the threshold location. The validity and the stability against further step of replica-symmetry breaking of the obtained results has been discussed thoroughly in [25,26].
The energy function used is taken to be proportional to the number of violated constraints and a satisfying assignment corresponds then to a zero-energy ground state:
E=X
a
Ea=X
a
Q3
i=1(1 +Jiasai)
2 , (1)
where sai is theith binary (spin) variable appearing in clausea and the coupling Jia takes the value 1 (respectively −1) if the corresponding variable appears not negated (respectively negated) in clause a. For instance, the clause (¯z1∨¯z2∨z3)
has an energy 18(1−s1)(1−s2)(1 +s3) and the Boolean variables zi ={0,1} are related to the spin variables by the transformationsi= (−1)zi.
The statistical mechanical analysis allows us to sketch the following phase dia- gram of the randomK-SAT problem. The numerical values of the critical parame- ters are given here for the caseK= 3 in which they are more accurately known, but the different phases and their ordering are preserved even for larger function-node connectivities.
For α < αf = 3.86, the T = 0 phase is at zero energy (the problem is SAT).
The entropy density is finite and the phase is replica symmetric (RS) and unfrozen.
There exists one giant cluster of nearby solutions and the effective fields over the variables vanish linearly with the temperature.
Atα= 3.86 a RSB instability appears. In the regionαf = 3.86< α < αd= 3.92 one expects a SAT phase with unfrozen variables [27,28].
Atαd '3.92 there is a discontinuous transition toward a clustered SAT frozen phase [2,12]. Up toαs= 4.15 the phase is 1-RSB unstable, while above it stabilizes [25]. ThecomplexityΣ, that is the normalized logarithm of the number of clusters, is finite in this region. At finite energy, the 1-RSB metastable states become unstable at the so-called Gardner energy density which constitutes a lower bound to the true dynamicalthreshold energy.
Atαc= 4.267 the ground state energy becomes positive and the random 3-SAT problem becomes generally UNSAT. At the same point the complexity vanishes. A new instability toward a full RSB phase appears finally atαS = 4.39.
Hard benchmarks for algorithm testing can be found in the small 1-RSB stable interval A = [αs, αS] [19] where the metastable states act as dynamical traps for local search processes.
2. The zero-energy SP equations
The SP equations are a formulation of the cavity equation which is valid for each specific instance and is able to provide information about the statistical behavior of the individual variables in the stable and metastable states of a given energy density.
The single sample analysis can be easily described in terms of the factor graph representation [29] in which the N variables i, j, k, . . .are represented by circular
‘variable nodes’, and the M clausesa, b, c, . . . are represented by square ‘function nodes’. For the standard random K-SAT, the function nodes have connectivity K, the variable nodes have an average Poisson connectivity Kα, but other degree distributions can be devised for specific purposes; the overall factor graph must anyway be always bipartite.
The messages passed from one function node a to a neighboring variable i are called cavity biases. They are Boolean numbers ua→i ∈ {0,1}, and being different from 0, only if it is absolutely needed that the variable i assumes a specific value in order to satisfya. The messages passed from one variable nodejof connectivity γj to a neighboring function nodeaare on the other hand called cavity fields and can assume integer values−γj < hj→a< γj.
The values of the cavity fieldshj→a depend on the cavity biases received by the variablej from all the neighboring function nodesb, exceptb=a(hence the name
‘cavity’):
hj→a=
X
b∈V+(j)\a
ub→j
−
X
b∈V−(j)\a
ub→j
. (2)
The sets V±(j) contain all the function nodes b neighboring to j such that the couplingJjb=±1 respectively. If j has no neighbor other thana, thenhj→a= 0.
The values of the cavity biasesua→i depend on the cavity fields received by the function nodeafrom all the neighboring variable nodesj, exceptj=i. If there is at least one literal satisfying already the clausea, that is if there existsj∈V(a)\i such that hj→aJja ≤0, thenua→i = 0, otherwise a warning must be sent toiand thenua→i= 1. Thus
ua→i= Y
j∈V(a)\i
θ¡
hj→aJja¢
, (3)
whereθ(x) is a step function taking valuesθ(x) = 0 forx≤0,θ(x) = 1 forx >0, andV(a) is the set of variable nodes neighboring the clausea. Ifahas no neighbor other thani, thenua→i= 1.
The probability distribution function, oru-survey, of the cavity biasua→ican be formally (but not constructively) written as
Qa→i(u) = 1 Ncl
X
`
δ(u, u`a→i), (4)
where ` runs over all clusters of solutions and u`a→i is the value assumed by the cavity bias over the edge a → i in the cluster `; δ denotes the Kronecker delta function over discrete variables, δ(x, y) = 1 if x = y and zero otherwise. It is important to remark that if a variablei is frozen inside a specific cluster `, there must be at least one clause a such that u`a→i = 1, in order to force i to assume the specific value satisfying a. On the other side, if all the cavity biases u`a→i = 0, the variable i is unfrozen in the cluster `, and its truth value is completely unconstrained. We shall write
Qa→i(u) = (1−ηa→i)δ(u,0) +ηa→iδ(u,1). (5) Au-survey will be then parametrized with a single real numberηa→i, which gives the probability of having a cavity bias traveling along the edge a → i when the existence of many clusters is taken into account.
In order to compute theu-survey (5) one needs to evaluate the probability that Jjahj→ais strictly positive for everyj∈V(a)\i, according to (3). Two assumptions must now be made. We shall assume that the cavity messages entering any given function node are uncorrelated, as it would happen if the factor graph was a tree. It is expected anyway that this approximation continues to be reasonable if the graph is locally tree-like, and no loops of size shorter than logarithmic in the graph size
are present (as in the case of the random graph ensembles under consideration).
We shall assume moreover to work at zero temperature. All the surveys will be computed assigning zero measure to all the set of messages driving toward states containing internal contradictions.
Under these conditions, it becomes possible to obtain a closed set of equations for theu-surveys, which can be suitably solved by an iterative procedure [13]:
ηa→i= Y
j∈V(a)\i
"
Wj→a±
Wj→a± +Wj→a∓ +Wj→a0
#
, (6)
where the signs±are chosen depending on whetherJja=±1 and where
Wj→a± =
1−λ Y
b∈V±(j)\a
(1−ηb→j)
Y
b∈V∓(j)
(1−ηb→j),
Wj→a0 =λ Y
b∈V(j)\a
(1−ηb→j). (7)
Theinterpolation parameter λ, whose meaning will be soon clarified, takes here the valueλ= 1.
It is useful to remark that a product likeQ
b∈V∓(j)(1−ηb→j) gives the probability that no warning arrives onj from the function nodesb∈V∓(j). The fundamental difference between the SP iterative equations (6) and (7) and the usual BP iter- ation lies exactly in the possibility (taken into account separately by SP) that no warnings are traveling along some edge. Indeed setting λ= 0 would give exactly the BP recursions. Interestingly, it turns out from numerical experiments that sometimes it can be useful to setλat some intermediate real value, as we shall see in§4, although no precise physical interpretation is available for these ‘hybridized’
equations.
Moving now to the description of the algorithm itself:
1. One starts initializing in a random way the value of ηa→j for every edge in the factor graph.
2. The set of edges is then swept in a random order and the cavity bias surveys updated sequentially using the relations (6) and (7).
3. When the variation ofηa→i between two subsequent sweeps becomes smaller than a given tolerance²for every edge, convergence is reached and the set of fixed-point u-surveys is denoted by{ηa→i∗ }.
At this point, the total bias acting over a variable can be easily evaluated. The fractions of clustersHi±,0 in which the variablei is respectively frozen in the + or
−direction, or is unfrozen read respectively:
Hi± = Wci±
Wci++cWi−+Wci0, Hi0= 1−Wci+−Wci−, (8)
where the quantitiesWci±,0 are a function of the whole set of fixed-pointu-surveys:
cWi±=
1−λ Y
a∈V±(i)
(1−ηa→i∗ )
Y
b∈V∓(i)
(1−ηa→i∗ ),
Wci0=λ Y
a∈V(i)
(1−ηa→i∗ ). (9)
The decimation part of the algorithm can then be finally summarized:
1. For all the variablesicompute the biases¯
¯Hi+−Hi−¯
¯using (8) and rank them from the most biased to the least biased.
2. Fix a predefined number of the most biased variables according to the di- rection of their bias and perform the resulting simplification of the factor graph.
The steps from 1 to 5 are repeated until a full assignment is produced or until convergence is lost or a paramagnetic state is reached (all the local biases vanish), in which case the left subproblem is passed to some local search heuristics, like Walksat, for completing the construction of a solution.
3. SP as RS equations over an extended state space
As seen in the preceding section, the main difference between SP and the bet- ter known BP method (which corresponds to a replica symmetric version of SP) lies in the existence of some ‘null’ message reflecting the possibility of having un- frozen variables. This physical intuition can be elucidated by a formal proof of strict equivalence between the SP results and the predictions of BP over a modified model [30].
We start by considering a configuration space of 3-valued variables σi ∈ {−1,∗,1,} instead ofsi ∈ {−1,1}, promoting the condition of being unfrozen to the rank of a genuine variable state.
Starting from a K-SAT factor graph V, we define a new problem G, endowed with alocal equilibrium condition (LEC) cost-energy function:
Eˆ = XM
a=1
Eˆa+ XN
i=1
Ai, (10)
where a new set of function nodes has been added:
Ai=δσi,∗(1−δE−1
i ,Ei1) + X
s=±1
δσi,sθ¡
Eis−Ei−s¢
. (11)
The quantityEi±1is defined as the sum of the energies of all the clauses neighboring the variableiwhenσi=±1, respectively. It is important to remark that the newad hoc introduced energy terms Ai are always local, depending only upon the second
neighbors of the variables i. In order to build again a locally tree-like structure, needed for the correct implementation of message-passing techniques, a duality transformation has to be performed [30].
It is remarkable that the BP equations written over the extended model are per- fectly equivalent to the SP equations written over original one. The new marginals PBP(σi = −1,∗,1) predicted by BP coincide, respectively, with Hi−,0,+ given by (8). Moreover, the Bethe approximation to the entropy on the extended problem coincides with the complexity Σ, giving the logarithm of the number of clusters of solutions predicted by SP. Once again the interested reader is invited to refer to [30] for the details of the computation.
4. SP with external fields
The standard SP algorithm described in §2 is a powerful tool for the efficient de- termination of a truth value assignment. Even in the case of large formulas very close to the SAT/UNSAT transition point, the SP-inspired decimation is able to fix a large fraction of the variables, producing a smaller and easily solvable sub- problem as the output. This is enough when one is just interested in finding at leastone solution, but in many tasks the determination of a set of several satisfying assignments, eventually distant among them, can be required. The algorithm must then be generalized if one is interested in driving the decimation process toward a desired region of the space of the possible assignments.
One may modify the SP iterations in order to accept a fixed externalprobability preconditioning. The original factor graph is modified connecting to each variable nodei an additional function nodexi, characterized by a coupling constantJixi=
±1, and injecting into the system a new u-survey ηxi→i of a predefined value.
The forcing realized by the conditioning nodes can be written as a vector field X, whose direction is given by the signs of the couplingsJixi and whose intensity is defined as the average value of ηxi→i. When updating the ordinary u-surveys ηa→i, these additional parametersηxi→i enter eqs (6) and (7) together with all the other ηs internal to the original factor graph, but they are never updated during the decimation process and their value is kept constant in time. They are simply
‘switched off’ when the associated variable is fixed and the factor graph accordingly simplified. The presence of the external probability conditionings tries to drive the evolution of the cavity bias distributions toward the selection of clusters in which the variables are maximally aligned with the externally imposed directionX.
It is interesting to use the modified SP iterations for probing the geometrical structure of the space of ground state assignments of K-SAT. A first experiment can be performed in which an external forcing X of random direction and small uniform intensity approximately equal toη(X)= 0.1 is imposed. A solutionSX is typically retrieved, at a Hamming distance
d(SX,X) = 1 2N
à 1−X
i
s(Si X)Jixi
!
(12) which is always significantly smaller than 0.5, signaling a nonrandom correlation betweenSX andX.
The distance d(SX,X) will be denoted in the following as dp and referred as thea prioridistortion. If the experiment is repeated with different random fields X1,X2, . . . ,X` one obtains in general `different solutionsSXi. If the selectedK- SAT formula presents a clustered phase thea prioridistortiondpbetween a solution and its corresponding forcing will be smaller than the typical distance d0 between two different solutionsSXiandSXj.
In the case of formulas extracted from the ensemble of random graphs described in
§1, the distance scaled0 is approximately 0.39 (average value of the inter-solution distance), which is smaller than 0.5, indicating that the retrieved solutions are concentrated along a preferential direction in the configuration space. This effect is due to the fact that the number of clausesb−i in which a variableiappears negated is not always exactly identical to the number of clauses b+i in which it appears directed. The cluster distribution is then concentrated preferentially in a hyper- cone centered around a direction b individuated by the signs of the differences b+i −b−i .
The distance scaled0 typical of the solutions lying inside a given cluster can be measured with a different experimental set-up. One starts determining a random solutionS. At this point, a forcing XdS is generated by taking the solutionS and flipping randomly N d of its spins. A decimation is then performed imposing the resulting forcing with a not too large intensity, and retrieving a new solutionSd.
The Hamming distance between Sd and S can be plotted against d. Whendis not too large it appears evident thatSd continues to belong to the same cluster as S. After a certain critical dc the retrieved solution escapes form the cluster and the distance from S increases. The difference between a typical f-RSB geometry and a 1-RSB landscape arises: for a formula taken in the frozen f-RSB phase after a critical distance dc, there is a continuum spectrum of inter-solution distances between an intra-cluster distance scale d1 and the inter-cluster distance scale d0. In the case of a formula in the 1-RSB stable region the transition betweend1 and d0becomes sharp (although some noise due to the tails of the distance probability distributions is present for finite sizes).
A further confirmation of the clustering hypothesis comes from the analysis of the reciprocal distances between different solutions. Two solutions Sd taken from the
‘intra-cluster plateau’ (d < dc) are found to be at a distance close to the measured value ofd1; the distance between a solutionSd with d < dc and another one with d > dc is on the other hand significantly larger than the scaled1 (it is of scale d0
in the 1-RSB case).
5. Using clusters for computational purposes
The capacity of the generalized SP of addressing the clustered structure of the ground state space can be exploited for computational purposes.
For formulas belonging to the 1-RSB stable region one expects dc À d0. This means that a ground state corrupted in no more thandcvariable positions can still be used for addressing the same cluster as the original solution S. A decimation procedure conducted using the corrupted vector as forcing can then be performed in order to produce a new vector S0 which will be only at distance d0 from the
correct solution S. A careful choice of the factor graph allows us to obtain quite remarkable solution-reconstruction capabilities, i.e. a lossy data compressor, as follows.
Let us consider a random binary vectorVand a given fixed factor graph. Let us impose a forcing field of moderate intensity along the direction V. A solutionSV
will be obtained, at the typical a priori distance dp from the forcing V. Suppose now we take as forcing a subvectorC, composed of just the firstN Rcomponents of the solutionSV. IfN Ris larger than a certain criticalN Rcand if the forcing along C is sufficiently intense, a new vectorV0 still belonging to the same cluster of SV
will be retrieved, lying consequently at a distance of orderd0from SV. Instead of performing a complete decimation in the decoding stage, one might just impose a really strong forcingC(ηdec'1) and fix all the variables according to the ranking obtained after the first convergence. Becaused0¿dp, the reconstructed stringV0 will be still at a distance from the originalVcomparable withdp.
The whole procedure can be considered as a lossy compression–decompression cycle [31]. The initial forcing vectorVcan be considered as a signal block emitted from a random uncorrelated binary source, and the solution chunkCplays the role of a compressed block. After the decoding stage, one retrieves finallyV0 as a de- compressed string. If the critical compression rateRcand thea prioridistortiondp
are small enough, and if the algorithm parametersηcodandηdecare carefully tuned, one can obtain a large compression factor without having too large a distortion. It should be noticed that this algorithm, exploiting the built-in quantization of the so- lution space, makes use of message-passing techniques both in the compression and in the decompression stage, differently from the case of LDPC and Turbo codes in which algorithms analogue to BP are used only for the decoding part [3,8]. Details about performance can be found in ref. [32].
6. Conclusion
The SP algorithm has proven to be an extremely powerful tool for the resolution of various combinatorial optimization problem presenting a clustered phase. While the associated proliferation of metastable states is harmful for local search heuristics, the SP procedure (based from the very beginning on an ansatz equivalent at a 1-RSB description) can successfully determine the most biased variables and construct a satisfying assignment by decimation. This is made possible by the introduction of the notion of frozen and unfrozen variables, as it can be shown rigorously by a formal proof of equivalence between SP and BP over an extended configurational space.
The extension of SP which make use of external probability conditionings, al- lows us to probe the geometrical structure of the solution space at a very fine level of detail, confirming the theoretical scenarios predicted by the cavity-replica theory.
Finally, the capability of SP to address selectively specific glassy clusters/states can be used for computational purposes. For instance, a simple (new) lossy com- pressor can be designed with non-trivial performance. Other applications are under study.
Acknowledgements
Credit for the results mentioned in this paper should be shared with M Mezard, A Braunstein, G Parisi, D Battaglia and J Chavas. The author thanks M Leone, A Pagnani, M Weigt, F Ricci-Tersenghi, A Montanari, D Achlioptas, N Brunel, S Mertens, C Baldassi and L Leuzzi for useful discussions.
References
[1] Special Issue onNP-hardness and phase transitionsedited by O Dubois, R Monasson, B Selman and R Zecchina,Theor. Comp. Sci.265(1–2)(2001)
[2] M M´ezard, G Parisi and R Zecchina,Science297, 812 (2002) (Sciencexpress published on-line 27-June-2002; 10.1126/science.1073287)
[3] N Sourlas,Nature (London)339, 693 (1989)
[4] H Nishimori, Statistical physics of spin glasses and information processing (Oxford University Press, 2001)
[5] C Papadimitriou and S Steiglitz,Combinatorial optimization(Dover, Mincola, New York, 1998)
[6] T Hogg, B A Huberman and C Williams (eds), Artificial Intelligence 81(I&II) (1996)
[7] D A Spielman,Lecture Notes in Computer Science1279, 67 (1997)
[8] T Richardson and R Urbanke, An introduction to the analysis of iterative coding systems, inCodes, systems, and graphical modelsedited by B Marcus and J Rosenthal (Springer, New York, 2001)
[9] N Ajtai,Electronic Colloquium on Computational Complexity (ECCC)7, 3 (1996) [10] R Monasson, R Zecchina, S Kirkpatrick, B Selman and L Troyansky,Nature (London)
400, 133 (1999)
[11] S Cocco, R Monasson, A Montanari and G Semerjian,Approximate analysis of search algorithms with ‘physical’ methods, preprint cs.CC/0302003 (2003)
[12] M M´ezard and R Zecchina,Phys. Rev.E66, 056126 (2002)
[13] A Braunstein, M M´ezard and R Zecchina, Survey propagation: an algorithm for satisfiability, preprint 2002, to appear in Random Structures and Algorithms, cs.CC/0212002
[14] R Motwani and P Raghavan, Randomized algorithms (Cambridge University Press, Cambridge, 2000)
[15] W Barthel, A K Hartmann and M Weigt, Solving satisfiability problems by fluctu- ations: An approximate description of the dynamics of stochastic local search algo- rithms, cond-mat/0301271, preprint (2003)
[16] M M´ezard and G Parisi,J. Stat. Phys.111, 1 (2003) [17] S Kirkpatrick and B Selman,Science264, 1297 (1994)
[18] J S Yedidia, W T Freeman and Y Weiss, Generalized belief propagation, inAdvances in neural information processing systems 13edited by T K Leen, T G Dietterich and V Tresp (MIT Press, 2001), pp. 689–695
[19] D Battaglia, M Kol´aˇr and R Zecchina,Minimizing energy below the glass thresholds, preprint cond-mat/0402529, to appear onPhys. Rev. E
[20] E Friedgut,J. Am. Math. Soc.12, 1017 (1999)
[21] O Dubois, Y Boufkhad and J Mandler, Typical random 3-SAT formulae and the satisfiability threshold, inProc. 11th ACM-SIAM Symp. on Discrete Algorithms, 124 (San Francisco, CA, 2000)
A Kaporis, L Kirousis and E Lalas, The probabilistic analysis of a greedy satisfiability algorithm, inProc. 4th European Symposium on Algorithms(ESA 2002), to appear in series: Lecture Notes in Computer Science, Springer
[22] F Guerra,Comm. Math. Phys.233, 1 (2003) S Franz and M Leone,J. Stat. Phys.111, 535 (2003) [23] J Franco,Theoret. Comput. Sci.265, 147 (2001)
D Achlioptas and G Sorkin,41st Annu. Symp. of Foundations of Computer Science, (IEEE Computer Soc. Press, Los Alamitos, CA, 2000), pp. 590–600
[24] D Achlioptas and C Moore, Random k-SAT: Two moments suffice to cross a sharp threshold, preprint (2002)
[25] A Montanari, G Parisi and F Ricci-Tersenghi,J. Phys.A37, 2073 (2004)
[26] S Mertens, M M´ezard and R Zecchina,Threshold values of random K-SAT from the cavity method, preprint, cs.CC/0309020 (2003)
[27] G Biroli, R Monasson and M Weigt,Eur. Phys. J.B14, 551 (2000)
[28] G Parisi, Some remarks on the survey decimation algorithm for K-satisfiability, preprint cs.CC/0301015 (2003).
[29] F R Kschischang, B J Frey and H-A Loeliger,IEEE Trans. Inf. Theory47, 498 (2002) [30] A Braunstein and R Zecchina,J. Stat. Mech.(2004) P06007
[31] D J C MacKay, Information theory, inference, and learning algorithms(Cambridge University Press, Cambridge, MA, 2003)
[32] D Battaglia, A Braunstein, J Chavas and R Zecchina, preprint cond-mat/0412652 (2004)
