The cavity method for large deviations

Abstract

A method is introduced for studying large deviations in the context of statistical physics of disordered systems. The approach, based on an extension of the cavity method to atypical realizations of the quenched disorder, allows us to compute exponentially small probabilities (rate functions) over different classes of random graphs. It is illustrated with two combinatorial optimization problems, the vertex-cover and coloring problems, for which the presence of replica symmetry breaking phases is taken into account. Applications include the analysis of models on adaptive graph structures.

18 pages, 7 figures

References in corpus (20)

• Random graphs with arbitrary degree distributions and their applications
• The Bethe lattice spin glass revisited
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Large Deviation of the Density Profile in the Steady State of the Open Symmetric Simple Exclusion Process
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Boosting search by rare events
• Core percolation in random graphs: a critical phenomena analysis
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• On large deviation properties of Erdos-Renyi random graphs
• Random Graph Coloring - a Statistical Physics Approach
• Higher-order QED corrections to single-W production in electron-positron collisions
• Statistical mechanics of the vertex-cover problem
• Large deviations in spin-glass ground-state energies
• Properties of atypical graphs from negative complexities
• Slowly evolving random graphs II: Adaptive geometry in finite-connectivity Hopfield models

Cited by in corpus (13)

• Landscape of solutions in constraint satisfaction problems
• Quiet Planting in the Locked Constraint Satisfaction Problems
• On the number of circuits in random graphs
• Ensemble inequivalence in random graphs
• Statistical mechanics of error exponents for error-correcting codes
• Exactly solvable models of adaptive networks
• Fluctuations in the random-link matching problem
• Reversible first-order transition in Pauli percolation
• Adversarial Satisfiability Problem
• Large deviations of the free energy in the p-spin glass spherical model
• Replica-symmetry breaking transitions in the large deviations of the ground-state of a spherical spin-glass
• Belief propagation for supply networks: Efficient clustering of their factor graphs
• Error Exponents of Low-Density Parity-Check Codes on the Binary Erasure Channel