A model is proposed for the evolution of the profile of a growing interface. The deterministic growth is solved exactly, and exhibits nontrivial relaxation patterns. The stochastic version is studied by dynamic renormalization-group techniques and by mappings to Burgers's equation and to a random directed-polymer problem. The exact dynamic scaling form obtained for a one-dimensional interface is in excellent agreement with previous numerical simulations. Predictions are made for more dimensions.

Numerical models indicate that collective animal behavior may emerge from simple local rules of interaction among the individuals. However, very little is known about the nature of such interaction, so that models and theories mostly rely on aprioristic assumptions. By reconstructing the three-dimensional positions of individual birds in airborne flocks of a few thousand members, we show that the interaction does not depend on the metric distance, as most current models and theories assume, but rather on the topological distance. In fact, we discovered that each bird interacts on average with a fixed number of neighbors (six to seven), rather than with all neighbors within a fixed metric distance. We argue that a topological interaction is indispensable to maintain a flock's cohesion against the large density changes caused by external perturbations, typically predation. We support this hypothesis by numerical simulations, showing that a topological interaction grants significantly higher cohesion of the aggregation compared with a standard metric one.

We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio alpha of clauses to variables less than a threshold alphac are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below alphac, where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.

From bird flocks to fish schools, animal groups often seem to react to environmental perturbations as if of one mind. Most studies in collective animal behavior have aimed to understand how a globally ordered state may emerge from simple behavioral rules. Less effort has been devoted to understanding the origin of collective response, namely the way the group as a whole reacts to its environment. Yet, in the presence of strong predatory pressure on the group, collective response may yield a significant adaptive advantage. Here we suggest that collective response in animal groups may be achieved through scale-free behavioral correlations. By reconstructing the 3D position and velocity of individual birds in large flocks of starlings, we measured to what extent the velocity fluctuations of different birds are correlated to each other. We found that the range of such spatial correlation does not have a constant value, but it scales with the linear size of the flock. This result indicates that behavioral correlations are scale free: The change in the behavioral state of one animal affects and is affected by that of all other animals in the group, no matter how large the group is. Scale-free correlations provide each animal with an effective perception range much larger than the direct interindividual interaction range, thus enhancing global response to perturbations. Our results suggest that flocks behave as critical systems, poised to respond maximally to environmental perturbations.

We prove the equivalence, near the critical point, of a $D$-dimensional spin system in a random external magnetic field with a ($D\ensuremath{-}2$)-dimensional spin system in the absence of a magnetic field. This is due to the hidden supersymmetry of the associated stochastic differential equation. We identify a space with one anticommuting coordinate with a space having negative dimensions -2.

The breaking of the replica symmetry in spin glasses is studied. It is found that the order parameter is a function on the interval 0-1. This approach is used to study the Sherrington-Kirkpatrick model. Exact results are obtained near the critical temperature. Approximated results at all the temperatures are in excellent agreement with the computer simulations at zero external magnetic field.

An order parameter for spin-glasses is defined in a clear physical way: It is a function on the interval 0-1 and it is related to the probability distribution of the overlap of the magnetization in different states of the system. It is shown to coincide with the order parameter introduced by use of the broken replica-symmetry approach.

So far the problem of a spin glass on a Bethe lattice has been solved only at the replica symmetric level, which is wrong in the spin glass phase. Because of some technical difficulties, attempts at deriving a replica symmetry breaking solution have been confined to some perturbative regimes, high connectivity lattices or temperature close to the critical temperature. Using the cavity method, we propose a general non perturbative solution of the Bethe lattice spin glass problem at a level of approximation which is equivalent to a one step replica symmetry breaking solution. The results compare well with numerical simulations. The method can be used for many finite connectivity problems appearing in combinatorial optimization.

It is generally argued that the energy dissipation of three-dimensional turbulent flow is concentrated on a set with non-integer Hausdorff dimension. Recently, in order to explain experimental data, it has been proposed that this set does not possess a global dilatation invariance: it can be considered to be a multifractal set. The authors review the concept of multifractal sets in both turbulent flows and dynamical systems using a generalisation of the beta -model.