Phase transition in the countdown problem

We present a combinatorial decision problem, inspired by the celebrated quiz show called Countdown, that involves the computation of a given target number T from a set of k randomly chosen integers along with a set of arithmetic operations. We find that the probability of winning the game evidences a threshold phenomenon that can be understood in the terms of an algorithmic phase transition as a function of the set size k. Numerical simulations show that such probability sharply transitions from zero to one at some critical value of the control parameter, hence separating the algorithm's parameter space in different phases. We also find that the system is maximally efficient close to the critical point. We derive analytical expressions that match the numerical results for finite size and permit us to extrapolate the behavior in the thermodynamic limit.

Thermodynamic glass transition in a spin glass without time-reversal symmetry

Spin glasses are a longstanding model for the sluggish dynamics that appear at the glass transition. However, spin glasses differ from structural glasses in a crucial feature: they enjoy a time reversal symmetry. This symmetry can be broken by applying an external magnetic field, but embarrassingly little is known about the critical behavior of a spin glass in a field. In this context, the space dimension is crucial. Simulations are easier to interpret in a large number of dimensions, but one must work below the upper critical dimension (i.e., in d < 6) in order for results to have relevance for experiments. Here we show conclusive evidence for the presence of a phase transition in a four-dimensional spin glass in a field. Two ingredients were crucial for this achievement: massive numerical simulations were carried out on the Janus special-purpose computer, and a new and powerful finite-size scaling method.

Sample-to-sample fluctuations of the overlap distributions in the three-dimensional Edwards-Anderson spin glass

We study the sample-to-sample fluctuations of the overlap probability densities from large-scale equilibrium simulations of the three-dimensional Edwards-Anderson spin glass below the critical temperature. Ultrametricity, stochastic stability, and overlap equivalence impose constraints on the moments of the overlap probability densities that can be tested against numerical data. We found small deviations from the Ghirlanda Guerra predictions, which get smaller as system size increases. We also focus on the shape of the overlap distribution, comparing the numerical data to a mean-field-like prediction in which finite-size effects are taken into account by substituting delta functions with broad peaks.

Static versus dynamic heterogeneities in the D=3 Edwards-Anderson-ising spin glass

We numerically study the aging properties of the dynamical heterogeneities in the Ising spin glass. We find that a phase transition takes place during the aging process. Statics-dynamics correspondence implies that systems of finite size in equilibrium have static heterogeneities that obey finite-size scaling, thus signaling an analogous phase transition in the thermodynamical limit. We compute the critical exponents and the transition point in the equilibrium setting, and use them to show that aging in dynamic heterogeneities can be described by a finite-time scaling ansatz, with potential implications for experimental work.

Separation and fractionation of order and disorder in highly polydisperse systems

We study a polydisperse soft-spheres model for colloids by means of microcanonical Monte Carlo simulations. We consider a polydispersity as high as 24%. Although solidification occurs, neither a crystal nor an amorphous state are thermodynamically stable. A finite size scaling analysis reveals that in the thermodynamic limit: a the fluid-solid transition is rather a crystal-amorphous phase-separation, b such phase-separation is preceded by the dynamic glass transition, and c small and big particles arrange themselves in the two phases according to a complex pattern not predicted by any fractionation scenario.

Nature of the spin-glass phase at experimental length scales

We present a massive equilibrium simulation of the three-dimensional Ising spin glass at low temperatures. The Janus special-purpose computer has allowed us to equilibrate, using parallel tempering, L = 32 lattices down to T ≈ 0.64Tc. We demonstrate the relevance of equilibrium finite-size simulations to understand experimental non-equilibrium spin glasses in the thermodynamical limit by establishing a time-length dictionary. We conclude that non-equilibrium experiments performed on a time scale of one hour can be matched with equilibrium results on L ≈ 110 lattices. A detailed investigation of the probability distribution functions of the spin and link overlap, as well as of their correlation functions, shows that Replica Symmetry Breaking is the appropriate theoretical framework for the physically relevant length scales. Besides, we improve over existing methodologies to ensure equilibration in parallel tempering simulations.

Spin glasses on the hypercube

We present a mean field model for spin glasses with a natural notion of distance built in, namely, the Edwards-Anderson model on the diluted D-dimensional unit hypercube in the limit of large D. We show that finite D effects are strongly dependent on the connectivity, being much smaller for a fixed coordination number. We solve the nontrivial problem of generating these lattices. Afterward, we numerically study the nonequilibrium dynamics of the mean field spin glass. Our three main findings are the following: i the dynamics is ruled by an infinite number of time sectors, ii the aging dynamics consists of the growth of coherent domains with a nonvanishing surface-volume ratio, and iii the propagator in Fourier space follows the p4 law. We study as well the finite D effects in the nonequilibrium dynamics, finding that a naive finite size scaling ansatz works surprisingly well.

Critical properties of the four-state commutative random permutation glassy Potts model in three and four dimensions

We investigate the critical properties of the four-state commutative random permutation glassy Potts model in three and four dimensions by means of Monte Carlo simulations and a finite-size scaling analysis. By using a field programmable gate array, we have been able to thermalize a large number of samples of systems with large volume. This has allowed us to observe a spin-glass ordered phase in d=4 and to study the critical properties of the transition. In d=3, our results are consistent with the presence of a Kosterlitz-Thouless transition, but also with different scenarios: transient effects due to a value of the lower critical dimension slightly below 3 could be very important.

Condensados de Bose-Einstein em redes óticas: a transição superfluido-isolante de Mott em redes hexagonais e a classe de universalidade superfluido-vidro de Bose em 3D

Estudamos transições de fases quânticas em gases bosônicos ultrafrios aprisionados em redes óticas. A física desses sistemas é capturada por um modelo do tipo Bose-Hubbard que, no caso de um sistema sem desordem, em que os átomos têm interação de curto alcance e o tunelamento é apenas entre sítios primeiros vizinhos, prevê a transição de fases quântica superfluido-isolante de Mott (SF-MI) quando a profundidade do potencial da rede ótica é variado. Num primeiro estudo, verificamos como o diagrama de fases dessa transição muda quando passamos de uma rede quadrada para uma hexagonal. Num segundo, investigamos como a desordem modifica essa transição. No estudo com rede hexagonal, apresentamos o diagrama de fases da transição SF-MI e uma estimativa para o ponto crítico do primeiro lobo de Mott. Esses resultados foram obtidos usando o algoritmo de Monte Carlo quântico denominado Worm. Comparamos nossos resultados com os obtidos a partir de uma aproximação de campo médio e com os de um sistema com uma rede ótica quadrada. Ao introduzir desordem no sistema, uma nova fase emerge no diagrama de fases do estado fundamental intermediando a fase superfluida e a isolante de Mott. Essa nova fase é conhecida como vidro de Bose (BG) e a transição de fases quântica SF-BG que ocorre nesse sistema gerou muitas controvérsias desde seus primeiros estudos iniciados no fim dos anos 80. Apesar dos avanços em direção ao entendimento completo desta transição, a caracterização básica das suas propriedades críticas ainda é debatida. O que motivou nosso estudo, foi a publicação de resultados experimentais e numéricos em sistemas tridimensionais [Yu et al. Nature 489, 379 (2012), Yu et al. PRB 86, 134421 (2012)] que violam a lei de escala $\\phi= u z$, em que $\\phi$ é o expoente da temperatura crítica, $z$ é o expoente crítico dinâmico e $ u$ é o expoente do comprimento de correlação. Abordamos essa controvérsia numericamente fazendo uma análise de escalonamento finito usando o algoritmo Worm nas suas versões quântica e clássica. Nossos resultados demonstram que trabalhos anteriores sobre a dependência da temperatura de transição superfluido-líquido normal com o potencial químico (ou campo magnético, em sistemas de spin), $T_c \\propto (\\mu-\\mu_c)^\\phi$, estavam equivocados na interpretação de um comportamento transiente na aproximação da região crítica genuína. Quando os parâmetros do modelo são modificados de maneira a ampliar a região crítica quântica, simulações com ambos os modelos clássico e quântico revelam que a lei de escala $\\phi= u z$ [com $\\phi=2.7(2)$, $z=3$ e $ u = 0.88(5)$] é válida. Também estimamos o expoente crítico do parâmetro de ordem, encontrando $\\beta=1.5(2)$.

First-order transition in a three-dimensional disordered system

We present the first detailed numerical study in three dimensions of a first-order phase transition that remains first order in the presence of quenched disorder (specifically, the ferromagnetic-paramagnetic transition of the site-diluted four states Potts model). A tricritical point, which lies surprisingly near the pure-system limit and is studied by means of finite-size scaling, separates the first-order and second-order parts of the critical line. This investigation has been made possible by a new definition of the disorder average that avoids the diverging-variance probability distributions that plague the standard approach. Entropy, rather than free energy, is the basic object in this approach that exploits a recently introduced microcanonical Monte Carlo method.

First Order Phase Transition in a 3D disordered system

We present a detailed numerical study on the effects of adding quenched impurities to a three dimensional system which in the pure case undergoes a strong first order phase transition (specifically, the ferromagnetic/paramagnetic transition of the site-diluted four states Potts model). We can state that the transition remains first-order in the presence of quenched disorder (a small amount of it) but it turns out to be second order as more impurities are added. A tricritical point, which is studied by means of Finite-Size Scaling, separates the first-order and second-order parts of the critical line. The results were made possible by a new definition of the disorder average that avoids the diverging-variance probability distributions that arise using the standard methodology. We also made use of a recently proposed microcanonical Monte Carlo method in which entropy, instead of free energy, is the basic quantity.

Critical behavior of the specific heat in glass formers

We show numeric evidence that, at low enough temperatures, the potential energy density of a glass-forming liquid fluctuates over length scales much larger than the interaction range. We focus on the behavior of translationally invariant quantities. The growing correlation length is unveiled by studying the finite-size effects. In the thermodynamic limit, the specific heat and the relaxation time diverge as a power law. Both features point towards the existence of a critical point in the metastable supercooled liquid phase.

The dynamics of a genetic algorithm for a simple learning problem

A formalism for describing the dynamics of Genetic Algorithms (GAs) using method s from statistical mechanics is applied to the problem of generalization in a perceptron with binary weights. The dynamics are solved for the case where a new batch of training patterns is presented to each population member each generation, which considerably simplifies the calculation. The theory is shown to agree closely to simulations of a real GA averaged over many runs, accurately predicting the mean best solution found. For weak selection and large problem size the difference equations describing the dynamics can be expressed analytically and we find that the effects of noise due to the finite size of each training batch can be removed by increasing the population size appropriately. If this population resizing is used, one can deduce the most computationally efficient size of training batch each generation. For independent patterns this choice also gives the minimum total number of training patterns used. Although using independent patterns is a very inefficient use of training patterns in general, this work may also prove useful for determining the optimum batch size in the case where patterns are recycled.

Efficient Bayesian inference for learning in the Ising linear perceptron and signal detection in CDMA

Efficient new Bayesian inference technique is employed for studying critical properties of the Ising linear perceptron and for signal detection in code division multiple access (CDMA). The approach is based on a recently introduced message passing technique for densely connected systems. Here we study both critical and non-critical regimes. Results obtained in the non-critical regime give rise to a highly efficient signal detection algorithm in the context of CDMA; while in the critical regime one observes a first-order transition line that ends in a continuous phase transition point. Finite size effects are also studied. © 2006 Elsevier B.V. All rights reserved.

Genetics and competing strategies in a threshold model for mail processing

Multi-agent algorithms inspired by the division of labour in social insects are applied to a problem of distributed mail retrieval in which agents must visit mail producing cities and choose between mail types under certain constraints.The efficiency (i.e. the average amount of mail retrieved per time step), and the flexibility (i.e. the capability of the agents to react to changes in the environment) are investigated both in static and dynamic environments. New rules for mail selection and specialisation are introduced and are shown to exhibit improved efficiency and flexibility compared to existing ones. We employ a genetic algorithm which allows the various rules to evolve and compete. Apart from obtaining optimised parameters for the various rules for any environment, we also observe extinction and speciation. From a more theoretical point of view, in order to avoid finite size effects, most results are obtained for large population sizes. However, we do analyse the influence of population size on the performance. Furthermore, we critically analyse the causes of efficiency loss, derive the exact dynamics of the model in the large system limit under certain conditions, derive theoretical upper bounds for the efficiency, and compare these with the experimental results.