Search

In critical systems, the effect of a localized perturbation affects points that are arbitrarily far from the perturbation location. In this paper, we study the effect of localized perturbations on the solution of the random dimer problem in $2D$. By means of an accurate numerical analysis, we show that a local perturbation of the optimal covering induces an excitation whose size is extensive with finite probability. We compute the fractal dimension of the excitations and scaling exponents. In particular, excitations in random dimer problems on non-bipartite lattices have the same statistical properties of domain walls in the $2D$ spin glass. Excitations produced in bipartite lattices, instead, are compatible with a loop-erased self-avoiding random walk process. In both cases, we find evidence of conformal invariance of the excitations that is compatible with $\mathrm{SLE}_\kappa$ with parameter $\kappa$ depending on the bipartiteness of the underlying lattice only., Comment: 8 pages

We consider the problem of recovering an unknown $k$-factor, hidden in a weighted random graph. For $k=1$ this is the planted matching problem, while the $k=2$ case is closely related to the planted travelling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition., 21 pages, 4 figures

We consider the assignment problem between two sets of $N$ random points on a smooth, two-dimensional manifold $\Omega$ of unit area. It is known that the average cost scales as $E_{\Omega}(N)\sim\frac{1}{2\pi}\ln N$ with a correction that is at most of order $\sqrt{\ln N\ln\ln N}$. In this paper, we show that, within the linearization approximation of the field-theoretical formulation of the problem, the first $\Omega$-dependent correction is on the constant term, and can be exactly computed from the spectrum of the Laplace--Beltrami operator on $\Omega$. We perform the explicit calculation of this constant for various families of surfaces, and compare our predictions with extensive numerics., Comment: 34 pages, 7 figures

We consider the random Euclidean assignment problem on the line between two sets of $N$ random points, independently generated with the same probability density function $\varrho$. The cost of the matching is supposed to be dependent on a power $p>1$ of the Euclidean distance of the matched pairs. We discuss an integral expression for the average optimal cost for $N\gg 1$ that generalizes a previous result obtained for $p=2$. We also study the possible divergence of the given expression due to the vanishing of the probability density function. The provided regularization recipe allows us to recover the proper scaling law for the cost in the divergent cases, and possibly some of the involved coefficients. The possibility that the support of $\varrho$ is a disconnected interval is also analysed. We exemplify the proposed procedure and we compare our predictions with the results of numerical simulations., 18 pages, 12 figures

Using the replica approach and the cavity method, we study the fluctuations of the optimal cost in the random-link matching problem. By means of replica arguments, we derive the exact expression of its variance. Moreover, we study the large deviation function, deriving its expression in two different ways, namely using both the replica method and the cavity method., Comment: 9 pages, 3 figures

We study the random-link matching problem on random regular graphs, alongside with two relaxed versions of the problem, namely the fractional matching and the so-called "loopy" fractional matching. We estimated the asymptotic average optimal cost using the cavity method. Moreover, we also study the finite-size corrections due to rare topological structures appearing in the graph at large sizes. We estimate these contributions using the cavity approach, and we compare our results with the output of numerical simulations. The analysis also clarifies the meaning of the finite-size contributions appearing in the fully-connected version of the problem, that has been already analyzed in the literature.

We propose a class of mean-field models for the isostatic transition of systems of soft spheres, in which the contact network is modeled as a random graph and each contact is associated to $d$ degrees of freedom. We study such models in the hypostatic, isostatic, and hyperstatic regimes. The density of states is evaluated by both the cavity method and exact diagonalization of the dynamical matrix. We show that the model correctly reproduces the main features of the density of states of real packings and, moreover, it predicts the presence of localized modes near the lower band edge. Finally, the behavior of the density of states $D(\omega)\sim\omega^\alpha$ for $\omega\to 0$ in the hyperstatic regime is studied. We find that the model predicts a nontrivial dependence of $\alpha$ on the details of the coordination distribution., Comment: 15 pages, 14 figures

We consider two formulations of the random-link fractional matching problem, a relaxed version of the more standard random-link (integer) matching problem. In one formulation, we allow each node to be linked to itself in the optimal matching configuration. In the other one, on the contrary, such a link is forbidden. Both problems have the same asymptotic average optimal cost of the random-link matching problem on the complete graph. Using a replica approach and previous results of W\"{a}stlund [Acta Mathematica 204, 91-150 (2010)], we analytically derive the finite-size corrections to the asymptotic optimal cost. We compare our results with numerical simulations and we discuss the main differences between random-link fractional matching problems and the random-link matching problem., Comment: 24 pages, 3 figures

We discuss the optimal matching solution for both the assignment problem and the matching problem in one dimension for a large class of convex cost functions. We consider the problem in a compact set with the topology both of the interval and of the circumference. Afterwards, we assume the points' positions to be random variables identically and independently distributed on the considered domain. We analytically obtain the average optimal cost in the asymptotic regime of very large number of points $N$ and some correlation functions for a power-law type cost function in the form $c(z)=z^p$, both in the $p>1$ case and in the $p1$, whereas in both cases it is a constant when $p, 21 pages

We extend the free-energy formalism recently introduced for homogeneous Fokker–Planck equations to a wide class of inhomogeneous nonlinear Fokker–Planck equations, providing sufficient conditions for the equation coefficients to obtain a free-energy that does not increase with time. Some properties of the stationary solutions of these Fokker–Planck equations are discussed.

We analytically derive, in the context of the replica formalism, the first finite size corrections to the average optimal cost in the random assignment problem for a quite generic distribution law for the costs. We show that, when moving from a power-law distribution to a $\Gamma$ distribution, the leading correction changes both in sign and in its scaling properties. We also examine the behavior of the corrections when approaching a $\delta$-function distribution. By using a numerical solution of the saddle-point equations, we provide predictions that are confirmed by numerical simulations., Comment: 16 pages, 4 figures

We discuss a generalized representation of the Dirac delta function in $d$ dimensions in terms of $q$-exponential functions. We apply this new representation to the study of the so-called $q$-Fourier transform, proving its invertibility for any value of $d$. We finally illustrate the effect of the $q$-deformation on the Gibbs phenomenon., Comment: 6 pages, 3 figures

In the previous chapter we discussed optimization problems defined on graphs, and in particular matching problems. For each of these problems we supposed that the parameters of the problem (e.g., the weight matrix for the considered graph) were given once and for all. For a given instance of an optimization problem, the solution can be found running specific algorithms available in the literature.

In the previous chapter we presented some random optimization problems on weighted graphs and some useful tools for their solution. However, we did not discuss the effect of possible correlations among the weights associated to the edges of the considered graphs, or we supposed explicitly that no correlation at all was present.

The matching problem is an important combinatorial problem defined on a graph. Graphs provide very often a pictorial representation of the mathematical structure underlying combinatorial optimization problems. On the other hand, graph theory is by itself rich of elegant results that can give us useful insights on many combinatorial and physical problems. For these reasons, we present here a very short introduction to the basic definitions and results of graph theory. We will refer mostly to the standard textbook of Diestel [3].

We extend a recently introduced free-energy formalism for homogeneous Fokker-Planck equations to a wide, and physically appealing, class of inhomogeneous nonlinear Fokker-Planck equations. In our approach, the free-energy functional is expressed in terms of an entropic functional and an auxiliary potential, both derived from the coefficients of the equation. With reference to the introduced entropic functional, we discuss the entropy production in a relaxation process towards equilibrium. The properties of the stationary solutions of the considered Fokker-Planck equations are also discussed., Comment: 8 pages

We analyze the distribution that extremizes a linear combination of the Boltzmann--Gibbs entropy and the nonadditive $q$-entropy. We show that this distribution can be expressed in terms of a Lambert function. Both the entropic functional and the extremizing distribution can be associated with a nonlinear Fokker--Planck equation obtained from a master equation with nonlinear transition rates. Also, we evaluate the entropy extremized by a linear combination of a Gaussian distribution (which extremizes the Boltzmann--Gibbs entropy) and a $q$-Gaussian distribution (which extremizes the $q$-entropy). We give its explicit expression for $q=0$, and discuss the other cases numerically. The entropy that we obtain can be expressed, for $q=0$, in terms of Lambert functions, and exhibits a discontinuity in the second derivative for all values of $q, 8 pages, 3 figure

We propose a unifying picture where the notion of generalized entropy is related to information theory by means of a group-theoretical approach. The group structure comes from the requirement that an entropy be well defined with respect to the composition of independent systems, in the context of a recently proposed generalization of the Shannon-Khinchin axioms. We associate to each member of a large class of entropies a generalized information measure, satisfying the additivity property on a set of independent systems as a consequence of the underlying group law. At the same time, we also show that Einstein's likelihood function naturally emerges as a byproduct of our informational interpretation of (generally nonadditive) entropies. These results confirm the adequacy of composable entropies both in physical and social science contexts., Comment: 5 pages

We analyze the random Euclidean bipartite matching problem on the hypertorus in $d$ dimensions with quadratic cost and we derive the two-point correlation function for the optimal matching, using a proper ansatz introduced by Caracciolo et al. [Phys. Rev. E 90, 012118 (2014)] to evaluate the average optimal matching cost. We consider both the grid-Poisson matching problem and the Poisson-Poisson matching problem. We also show that the correlation function is strictly related to the Green's function of the Laplace operator on the hypertorus.

We introduce three deformations, called α -, β - and γ -deformation respectively, of a N -body probabilistic model, first proposed by Rodriguez et al. (2008), having q -Gaussians as N → ∞ limiting probability distributions. The proposed α - and β -deformations are asymptotically scale-invariant, whereas the γ -deformation is not. We prove that, for both α - and β -deformations, the resulting deformed triangles still have q -Gaussians as limiting distributions, with a value of q independent (dependent) on the deformation parameter in the α -case ( β -case). In contrast, the γ -case, where we have used the celebrated Q -numbers and the Gauss binomial coefficients, yields other limiting probability distribution functions, outside the q -Gaussian family. These results suggest that scale-invariance might play an important role regarding the robustness of the q -Gaussian family.

We propose a new approach for the study of the quadratic stochastic Euclidean bipartite matching problem between two sets of $N$ points each, $N\gg 1$. The points are supposed independently randomly generated on a domain $\Omega\subset\mathbb R^d$ with a given distribution $\rho(\mathbf x)$ on $\Omega$. In particular, we derive a general expression for the correlation function and for the average optimal cost of the optimal matching. A previous ansatz for the matching problem on the flat hypertorus is obtained as particular case., Comment: 5 pages + Supplemental material

We discuss the equivalence relation between the Euclidean bipartite matching problem on the line and on the circumference and the Brownian bridge process on the same domains. The equivalence allows us to compute the correlation function and the optimal cost of the original combinatorial problem in the thermodynamic limit; moreover, we solve also the minimax problem on the line and on the circumference. The properties of the average cost and correlation functions are discussed.

We provide a general theoretical framework allowing us to extend the classical Lie theory for partial differential equations to the case of equations of fractional order. We propose a general prolongation formula for the study of Lie symmetries in the case of an arbitrary finite number of independent variables. We also prove the Lie theorem in the case of fractional differential equations, showing that the proper space for the analysis of these symmetries is the infinite dimensional jet space., 14 pages

Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. In this manuscript, we characterise the learning of a mixture of K Gaussians with generic means and covariances via empirical risk minimisation (ERM) with any convex loss and regularisation. In particular, we prove exact asymptotics characterising the ERM estimator in high-dimensions, extending several previous results about Gaussian mixture classification in the literature. We exemplify our result in two tasks of interest in statistical learning: a) classification for a mixture with sparse means, where we study the efficiency of ℓ1 penalty with respect to ℓ2; b) max-margin multi-class classification, where we characterise the phase transition on the existence of the multi-class logistic maximum likelihood estimator for K>2. Finally, we discuss how our theory can be applied beyond the scope of synthetic data, showing that in different cases Gaussian mixtures capture closely the learning curve of classification tasks in real data sets.

International audience; The random energy model (REM) and the generalized random energy model (GREM) are simple spin glass models which play an important role in the theory of spin glasses. The connection with more complex spin glass models can be made using the pspin generalisation of the SK model, which, in the large p limit, gives precisely the REM. The REM and GREM allow us to illustrate and to test in a simple framework several central ideas of the theory both from an equilibrium and from a dynamical point of view. They were also used in several contexts such as the problem of protein folding or errorcorrecting codes. This chapter presents the basic ideas and some recent developments for two aspects: (1) The random energy models and replica symmetry breaking by B. Derrida and P. Mottishaw (2) Aging in the activated dynamics of the REM and the p-spin SK models by V. Gayrard To appear as a contribution (specifically, Chapter 31) to the edited volume ``Spin Glass Theory \& Far Beyond - Replica Symmetry Breaking after 40 Years'', World Scientific.