Search

Your search keyword '"Dipartimento di Fisica and INFM"' showing total 10 results
Start Over Author "Dipartimento di Fisica and INFM" Language undetermined
10 results on '"Dipartimento di Fisica and INFM"'

1. Biased landscapes for random constraint satisfaction problems

Author

Guilhem Semerjian, Louise Budzynski, Federico Ricci-Tersenghi, Laboratoire de Physique Théorique de l'ENS (LPTENS), Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Systèmes Désordonnés et Applications, Laboratoire de physique de l'ENS - ENS Paris (LPENS (UMR_8023)), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Université Paris Diderot - Paris 7 (UPD7)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Université Paris Diderot - Paris 7 (UPD7), Dipartimento di Fisica and INFM, and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]

Subjects
FOS: Computer and information sciences, Statistics and Probability, Phase transition, Discrete Mathematics (cs.DM), FOS: Physical sciences, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 0103 physical sciences, FOS: Mathematics, [PHYS.COND.CM-DS-NN]Physics [physics]/Condensed Matter [cond-mat]/Disordered Systems and Neural Networks [cond-mat.dis-nn], Limit (mathematics), Statistical physics, 010306 general physics, Cluster analysis, random constraint satisfaction problems, phase transitions, algorithmic complexity, ComputingMilieux_MISCELLANEOUS, Constraint satisfaction problem, Mathematics, Complexity of constraint satisfaction, Probability (math.PR), Statistical and Nonlinear Physics, Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, Tree (graph theory), Satisfiability, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], 010201 computation theory & mathematics, Simulated annealing, Statistics, Probability and Uncertainty, Mathematics - Probability, Computer Science - Discrete Mathematics
Abstract

The typical complexity of Constraint Satisfaction Problems (CSPs) can be investigated by means of random ensembles of instances. The latter exhibit many threshold phenomena besides their satisfiability phase transition, in particular a clustering or dynamic phase transition (related to the tree reconstruction problem) at which their typical solutions shatter into disconnected components. In this paper we study the evolution of this phenomenon under a bias that breaks the uniformity among solutions of one CSP instance, concentrating on the bicoloring of k-uniform random hypergraphs. We show that for small k the clustering transition can be delayed in this way to higher density of constraints, and that this strategy has a positive impact on the performances of Simulated Annealing algorithms. We characterize the modest gain that can be expected in the large k limit from the simple implementation of the biasing idea studied here. This paper contains also a contribution of a more methodological nature, made of a review and extension of the methods to determine numerically the discontinuous dynamic transition threshold., Comment: 32 pages, 16 figures

Published
2019
Full Text
View/download PDF

2. Universal Spectrum of Normal Modes in Low-Temperature Glasses: an Exact Solution

Author

Franz, Silvio, Parisi, Giorgio, Urbani, Pierfrancesco, Zamponi, Francesco, Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11), Dipartimento di Fisica and INFM, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Institut de Physique Théorique - UMR CNRS 3681 (IPHT), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Le Vaou, Claudine, Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA)

Subjects
[PHYS]Physics [physics], Condensed Matter::Soft Condensed Matter, Statistical Mechanics (cond-mat.stat-mech), Soft Condensed Matter (cond-mat.soft), FOS: Physical sciences, Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, Condensed Matter - Soft Condensed Matter, Condensed Matter - Statistical Mechanics, [PHYS] Physics [physics]
Abstract

We report an analytical study of the vibrational spectrum of the simplest model of jamming, the soft perceptron. We identify two distinct classes of soft modes. The first kind of modes are related to isostaticity and appear only in the close vicinity of the jamming transition. The second kind of modes instead are present everywhere in the glass phase and are related to the hierarchical structure of the potential energy landscape. Our results highlight the universality of the spectrum of normal modes in disordered systems, and open the way towards a detailed analytical understanding of the vibrational spectrum of low-temperature glasses., Comment: 6 pages, 3 figures, submitted to PNAS

Published
2015
Full Text
View/download PDF

3. Nondynamic Origin of the High-Frequency Acoustic Attenuation in Glasses

Author

Giulio Monaco, Frédéric Pignon, Tullio Scopigno, Daniele Fioretto, Michael Krisch, Claudio Masciovecchio, Francesco Sette, M. Lorenzen, Giancarlo Ruocco, R. Di Leonardo, Istituto Nazionale di Fisica della Materia, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], CNR-INFM CRS-SOFT, Universitá di Roma 'La Sapienza,', European Synchrotron Radiation Facility (ESRF), Dipartimento di Fisica [L'Aquila], Università degli Studi dell'Aquila (UNIVAQ), Research Center SOFT INFM-CNR, c/o Universita di Roma 'La Sapienza', Dipartimento di Fisica, Universita di Perugia, Università degli Studi di Perugia (UNIPG), Laboratoire de rhéologie (LR), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), Dipartimento di Fisica and INFM, and Università degli Studi di Trento (UNITN)

Subjects
Terahertz radiation, General Physics and Astronomy, XPCS, 02 engineering and technology, 01 natural sciences, Molecular physics, [SPI.MECA.MEFL]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Fluids mechanics [physics.class-ph], Molecular dynamics, Optics, 0103 physical sciences, [SPI.GPROC]Engineering Sciences [physics]/Chemical and Process Engineering, 010306 general physics, Sound wave, Physics, Range (particle radiation), Scattering, business.industry, Glasses, Attenuation, Silica, 021001 nanoscience & nanotechnology, sound attenuation, 0210 nano-technology, business, [PHYS.COND.CM-SCM]Physics [physics]/Condensed Matter [cond-mat]/Soft Condensed Matter [cond-mat.soft], Acoustic attenuation
Abstract

The sound attenuation in the THz region is studied down to T 16 K in glassy glycerol by inelastic x-ray scattering. At striking variance with the decrease found below 100 K in the GHz data, the attenuation in the THz range does not show any T dependence. This result (i) indicates the presence of two different attenuation mechanisms, active, respectively, in the high- and low-frequency limits, (ii) demonstrates the nondynamic origin of the attenuation of THz sound waves, and confirms a similar conclusion obtained in SiO2 glass by molecular dynamics, and (iii) supports the low-frequency attenuation mechanism proposed by Fabian and Allen [ Phys. Rev. Lett. 82, 1478 (1999)].

Published
1999
Full Text
View/download PDF

4. Quasi-equilibrium in glassy dynamics: An algebraic view

Author

Giorgio Parisi, Silvio Franz, Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11), Dipartimento di Fisica and INFM, and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]

Subjects
Statistics and Probability, Physics, Spin glass, Statistical Mechanics (cond-mat.stat-mech), Computation, Transition temperature, FOS: Physical sciences, Statistical and Nonlinear Physics, Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, 01 natural sciences, 010305 fluids & plasmas, Mean field theory, 0103 physical sciences, Statistical physics, Configuration space, [PHYS.COND.CM-SM]Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], Statistics, Probability and Uncertainty, Algebraic number, 010306 general physics, Langevin dynamics, Quasistatic process, Condensed Matter - Statistical Mechanics
Abstract

We study a chain of identical glassy systems in a constrained equilibrium where each bond of the chain is forced to remain at a preassigned distance to the previous one. We apply this description to Mean Field Glassy systems in the limit of long chain where each bond is close to the previous one. We show that in specific conditions this pseudo-dynamic process can formally describe real relaxational dynamics the long time. In particular, in mean field spin glass models we can recover in this way the equations of Langevin dynamics in the long time limit at the dynamical transition temperature and below. We interpret the formal identity as an evidence that in these situations the configuration space is explored in a quasi-equilibrium fashion. Our general formalism, that relates dynamics to equilibrium puts slow dynamics in a new perspective and opens the way to the computation of new dynamical quantities in glassy systems., A few typos corrected in the new version

Published
2013

5. Extreme Value Statistics Distributions in Spin Glasses

Author

Aurélien Decelle, Michele Castellana, Elia Zarinelli, Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11), Dipartimento di Fisica and INFM, and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]

Subjects
Physics, Spin glass, Statistical Mechanics (cond-mat.stat-mech), Condensed matter physics, Gaussian, FOS: Physical sciences, General Physics and Astronomy, Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, Condensed Matter::Disordered Systems and Neural Networks, 01 natural sciences, 010305 fluids & plasmas, Condensed Matter::Materials Science, symbols.namesake, Distribution (mathematics), Gumbel distribution, Point distribution model, 0103 physical sciences, symbols, Probability distribution, [PHYS.COND.CM-SM]Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], 010306 general physics, Extreme value theory, Random variable, Condensed Matter - Statistical Mechanics
Abstract

International audience; We study the probability distribution of the pseudo-critical temperature in a mean-field and in a short-range spin-glass model: the Sherrington-Kirkpatrick (SK) and the Edwards-Anderson (EA) model. In both cases, we put in evidence the underlying connection between the fluctuations of the pseudo-critical point and and the Extreme Value Statistics of random variables. For the SK model, both with Gaussian and binary couplings, the distribution of the pseudo-critical temperature is found to be the Tracy-Widom distribution. For the EA model, the distribution is found to be the Gumbel distribution. Being the EA model representative of uniaxial magnetic materials with quenched disorder like $Fe_{0.5} Mn_{0.5} Ti O_3$ or $Eu_{0.5} Ba_{0.5} Mn O_3$, its pseudo-critical point distribution should be a priori experimentally accessible.

Published
2011
Full Text
View/download PDF

6. Renormalization group computation of the critical exponents of hierarchical spin glasses

Author

Michele Castellana, Giorgio Parisi, Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11), Dipartimento di Fisica and INFM, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Dipartimento di Fisica, and Università Roma I

Subjects
Physics, Spin glass, Critical phenomena, Computation, FOS: Physical sciences, Scale (descriptive set theory), Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, Renormalization group, 01 natural sciences, 010305 fluids & plasmas, Quantum electrodynamics, [PHYS.COND.CM-GEN]Physics [physics]/Condensed Matter [cond-mat]/Other [cond-mat.other], 0103 physical sciences, Functional renormalization group, Statistical physics, 010306 general physics, Critical dimension, Critical exponent
Abstract

The large scale behavior of the simplest non-mean-field spin-glass system is analyzed, and the critical exponent related to the divergence of the correlation length is computed at two loops within the $ϵ$-expansion technique with two independent methods. The techniques presented show how the underlying ideas of the renormalization group apply also in this disordered model, in such a way that an $ϵ$-expansion can be consistently set up. By pushing such calculation to high orders in $ϵ$, a consistent non-mean-field theory for such disordered system could be established, giving a substantial contribution the development of a predictive theory for real spin glasses.

Published
2010

7. Quasi equilibrium construction for the long time limit of glassy dynamics

Author

Federico Ricci-Tersenghi, Pierfrancesco Urbani, Silvio Franz, Giorgio Parisi, Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11), Dipartimento di Fisica and INFM, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Institut de Physique Théorique - UMR CNRS 3681 (IPHT), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA)

Subjects
Statistics and Probability, Closure (topology), FOS: Physical sciences, spin glasses (theory), Spherical model, Statistical physics, Condensed Matter - Statistical Mechanics, [PHYS]Physics [physics], Physics, Statistical Mechanics (cond-mat.stat-mech), Markov chain, Statistics, structural glasses (theory), Slow dynamics and aging (theory), Statistical and Nonlinear Physics, Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, 16. Peace & justice, BBGKY hierarchy, Mean field theory, Phase space, slow relaxation and glassy dynamic, Probability and Uncertainty, Relaxation (approximation), Statistics, Probability and Uncertainty, Equations for a falling body
Abstract

In this paper we review a recent proposal to understand the long time limit of glassy dynamics in terms of an appropriate Markov Chain. [1]. The advantages of the resulting construction are many. The first one is that it gives a quasi equilibrium description on how glassy systems explore the phase space in the slow relaxation part of their dynamics. The second one is that it gives an alternative way to obtain dynamical equations starting from a dynamical rule that is static in spirit. This provides a way to overcome the difficulties encountered in the short time part of the dynamics where current conservation must be enforced. We study this approach in detail in a prototypical mean field disordered spin system, namely the p-spin spherical model, showing how we can obtain the well known equations that describes its dynamics. Then we apply the same approach to structural glasses. We first derive a set of dynamical Ornstein-Zernike equations which are very general in nature. Finally we consider two possible closure schemes for them, namely the Hypernetted Chain approximation of liquid theory and a closure of the BBGKY hierarchy that has been recently introduced by G. Szamel. From both approaches we finally find a set of dynamical Mode-Coupling like equations that are supposed to describe the system in the long time/slow dynamics regime., Comment: 13 pages, 3 figures

Published
2015
Full Text
View/download PDF

8. On the cooling-schedule dependence of the dynamics of mean-field glasses

Author

Andrea Montanari, Federico Ricci-Tersenghi, Laboratoire de Physique Théorique de l'ENS [École Normale Supérieure] (LPTENS), Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Department of Electrical Engineering and Statistics, Stanford University, Dipartimento di Fisica and INFM, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Laboratoire de Physique Théorique de l'ENS (LPTENS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]

Subjects
Physics, Schedule, Spin glass, Condensed matter physics, Statistical Mechanics (cond-mat.stat-mech), Computation, FOS: Physical sciences, Statistical mechanics, Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, Condensed Matter Physics, Threshold energy, 01 natural sciences, 010305 fluids & plasmas, Electronic, Optical and Magnetic Materials, Mean field theory, Phase (matter), Metastability, 0103 physical sciences, [PHYS.COND.CM-SM]Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], 010306 general physics, Condensed Matter - Statistical Mechanics
Abstract

The low temperature phase of discontinuous mean-field spin glasses is characterized by the appearance of an exponential number of metastable states. Which ones among these states dominate the out-of-equilibrium dynamics of these systems? In order to answer this question, we compare high-precision numerical simulations of a diluted $p$-spin model with a cavity computation of the threshold energy. Our main conclusion is that the aging dynamics is dominated by different layers of metastable states depending on the cooling schedule. In order to perform our analysis, we present a method for computing the marginality condition of diluted spin glasses at non-zero temperature., Comment: 19 pages, 6 eps figures

Published
2004
Full Text
View/download PDF

9. Static replica approach to critical correlations in glassy systems

Author

Hugo Jacquin, Giorgio Parisi, Pierfrancesco Urbani, Francesco Zamponi, Silvio Franz, Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Matière et Systèmes Complexes (MSC (UMR_7057)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Fisica and INFM, Università degli Studi di Roma 'La Sapienza' [Rome], Laboratoire de Physique Théorique de l'ENS (LPTENS), Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11), Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Université Pierre et Marie Curie - Paris 6 (UPMC)-Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Matière et Systèmes Complexes (MSC), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Laboratoire de Physique Théorique de l'ENS [École Normale Supérieure] (LPTENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Physics, Statistical Mechanics (cond-mat.stat-mech), Gaussian, Computation, Replica, FOS: Physical sciences, General Physics and Astronomy, Disordered Systems and Neural Networks (cond-mat.dis-nn), Soft modes, Condensed Matter - Disordered Systems and Neural Networks, 01 natural sciences, 010305 fluids & plasmas, symbols.namesake, Mean field theory, 0103 physical sciences, symbols, Exponent, Field theory (psychology), Statistical physics, [PHYS.COND.CM-SM]Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], Physical and Theoretical Chemistry, 010306 general physics, Condensed Matter - Statistical Mechanics, Physical quantity
Abstract

We discuss the slow relaxation phenomenon in glassy systems by means of replicas by constructing a static field theory approach to the problem. At the mean field level we study how criticality in the four point correlation functions arises because of the presence of soft modes and we derive an effective replica field theory for these critical fluctuations. By using this at the Gaussian level we obtain many physical quantities: the correlation length, the exponent parameter that controls the Mode-Coupling dynamical exponents for the two-point correlation functions, and the prefactor of the critical part of the four point correlation functions. Moreover we perform a one-loop computation in order to identify the region in which the mean field Gaussian approximation is valid. The result is a Ginzburg criterion for the glass transition. We define and compute in this way a proper Ginzburg number. Finally, we present numerical values of all these quantities obtained from the Hypernetted Chain approximation for the replicated liquid theory., 34 pages, 1 figure - to be published on J.Chem.Phys. for a special issue on the Glass Transition

Published
2013
Full Text
View/download PDF

10. Clusters of solutions and replica symmetry breaking in randomk-satisfiability

Author

Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, Laboratoire de Physique Théorique de l'ENS [École Normale Supérieure] (LPTENS), Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Department of Electrical Engineering and Statistics, Stanford University, Dipartimento di Fisica and INFM, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Laboratoire de Physique Théorique de l'ENS (LPTENS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]

Subjects
FOS: Computer and information sciences, Statistics and Probability, Phase transition, Cavity method, FOS: Physical sciences, Computational Complexity (cs.CC), 01 natural sciences, 010305 fluids & plasmas, 0103 physical sciences, Entropy (information theory), Symmetry breaking, Statistical physics, [PHYS.COND.CM-SM]Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], 010306 general physics, Condensed Matter - Statistical Mechanics, Physics, Random graph, Statistical Mechanics (cond-mat.stat-mech), Replica, Solution set, Statistical and Nonlinear Physics, Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, Satisfiability, Computer Science - Computational Complexity, Statistics, Probability and Uncertainty
Abstract

We study the set of solutions of random k-satisfiability formulae through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We refine substantially this picture by: (i) determining the precise location of the clustering transition; (ii) uncovering a second `condensation' phase transition in the structure of the solution set for k larger or equal than 4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m=1 via a correspondence with the tree reconstruction problem) and new large-k expansions., Comment: 30 pages, 14 figures, typos corrected, discussion of appendix C expanded with a new figure

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results