Abstract:
The Random K-Satisfiability Problem, consisting in verifying the existence of an assignment of N Boolean variables that satisfy a set of M=alpha N random logical clauses containing K variables each, is studied using the replica symmetric framework of diluted disordered systems. We present an exact iterative scheme for the replica symmetric functional order parameter together for the different cases of interest K=2, K>= 3 and K>>1. The calculation of the number of solutions, which allowed us [Phys. Rev. Lett. 76, 3881 (1996)] to predict a first order jump at the threshold where the Boolean expressions become unsatisfiable with probability one, is thoroughly displayed. In the case K=2, the (rigorously known) critical value (alpha=1) of the number of clauses per Boolean variable is recovered while for K>=3 we show that the system exhibits a replica symmetry breaking transition. The annealed approximation is proven to be exact for large K.

Abstract:
We analytically derive the geometrical structure of the weight space in multilayer neural networks (MLN), in terms of the volumes of couplings associated to the internal representations of the training set. Focusing on the parity and committee machines, we deduce their learning and generalization capabilities both reinterpreting some known properties and finding new exact results. The relationship between our approach and information theory as well as the Mitchison--Durbin calculation is established. Our results are exact in the limit of a large number of hidden units, showing that MLN are a class of exactly solvable models with a simple interpretation of replica symmetry breaking.

Abstract:
We study analytically and numerically the statics and the off-equilibrium dynamics of spin models over finitely connected random graphs. We identify a threshold value for the connectivity beyond which the loop structure of the graph becomes thermodynamically relevant. Glauber dynamics simulations show that this loop structure is responsible for the onset of dynamical features of a local character (dynamical heterogeneities and spontaneous time scale separation), consistently with previous (experimental and numerical) studies of glasses and spin glasses in their approach to the low temperature phase.

Abstract:
In this paper we study the hard sphere packing problem in the Hamming space by the cavity method. We show that both the replica symmetric and the replica symmetry breaking approximations give maximum rates of packing that are asymptotically the same as the lower bound of Gilbert and Varshamov. Consistently with known numerical results, the replica symmetric equations also suggest a crystalline solution, where for even diameters the spheres are more likely to be found in one of the subspaces (even or odd) of the Hamming space. These crystalline packings can be generated by a recursive algorithm which finds maximum packings in an ultra-metric space. Finally, we design a message passing algorithm based on the cavity equations to find dense packings of hard spheres. Known maximum packings are reproduced efficiently in non trivial ranges of dimensions and number of spheres.

Abstract:
We propose a message-passing algorithm to compute the Hamiltonian expectation with respect to an appropriate class of trial wave functions for an interacting system of fermions. To this end, we connect the quantum expectations to average quantities in a classical system with both local and global interactions, which are related to the variational parameters and use the Bethe approximation to estimate the average energy within the replica-symmetric approximation. The global interactions, which are needed to obtain a good estimation of the average fermion sign, make the average energy a nonlocal function of the variational parameters. We use some heuristic minimization algorithms to find approximate ground states of the Hubbard model on random regular graphs and observe significant qualitative improvements with respect to the mean-field approximation.

Abstract:
It has been shown experimentally that a decimation algorithm based on Survey Propagation (SP) equations allows to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum-product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value -- $*$ -- when they are not forced by the combinatorial constraints. An appropriate ``local equilibrium condition'' cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by SP. These results may help to clarify the geometrical notion of clusters assumed by SP for the random K-SAT or random graph coloring (where it is conjectured to be exact) and helps to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact.

Abstract:
Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations that lead to close ties between computer science and statistical physics. This review aims at presenting the tools and concepts designed by physicists to deal with optimization or decision problems in an accessible language for computer scientists and mathematicians, with no prerequisites in physics. We first introduce some elementary methods of statistical mechanics and then progressively cover the tools appropriate for disordered systems. In each case, we apply these methods to study the phase transitions or the statistical properties of the optimal solutions in various combinatorial problems. We cover in detail the Random Graph, the Satisfiability, and the Traveling Salesman problems. References to the physics literature on optimization are provided. We also give our perspective regarding the interdisciplinary contribution of physics to computer science.

Abstract:
We relate the quantum dynamics of the Bose-Hubbard model (BHM) to the semiclassical nonlinear equations that describe an array of interacting Bose condensates by implementing a standard variational procedure based on the coherent state method. We investigate the dynamics of the two-site BHM from the purely quantum viewpoint by recasting first the model within a spin picture and using then the related dynamical algebra. The latter allows us to study thoroughly the energy spectrum structure and to interpret quantally the classical symmetries of the two-site dynamics. The energy spectrum is also evaluated through various approximations relying on the coherent state approach.

Abstract:
We study analytically a simple game theoretical model of heterogeneous interacting agents. We show that the stationary state of the system is described by the ground state of a disordered spin model which is exactly solvable within the simple replica symmetric ansatz. Such a stationary state differs from the Nash equilibrium where each agent maximizes her own utility. The latter turns out to be characterized by a replica symmetry broken structure. Numerical results fully agree with our analytic findings.

Abstract:
The use of parity-check gates in information theory has proved to be very efficient. In particular, error correcting codes based on parity checks over low-density graphs show excellent performances. Another basic issue of information theory, namely data compression, can be addressed in a similar way by a kind of dual approach. The theoretical performance of such a Parity Source Coder can attain the optimal limit predicted by the general rate-distortion theory. However, in order to turn this approach into an efficient compression code (with fast encoding/decoding algorithms) one must depart from parity checks and use some general random gates. By taking advantage of analytical approaches from the statistical physics of disordered systems and SP-like message passing algorithms, we construct a compressor based on low-density non-linear gates with a very good theoretical and practical performance.