Information, Physics, and Computation

DOI10.1093/acprof:oso/9780198570837.001.0001zbMath1163.94001OpenAlexW2566505556MaRDI QIDQ3611833

Marc Mézard, Andrea Montanari

Publication date: 3 March 2009

Full work available at URL: https://doi.org/10.1093/acprof:oso/9780198570837.001.0001

zbMATH Keywords

combinatorial optimizationinformationspin glassesIsing modelstatistical physicscoding theorylong-range correlationreplica theory

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to statistics (62-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory (94-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to statistical mechanics (82-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to numerical analysis (65-01)

Related Items

Modeling Network Populations via Graph Distances, Multilayer Modularity Belief Propagation to Assess Detectability of Community Structure, A closure for the master equation starting from the dynamic cavity method, The discrete random energy model and one step replica symmetry breaking, Satisfiability transition in asymmetric neural networks, The cavity method to protein design problem, Learning curves of generic features maps for realistic datasets with a teacher-student model*, Ising model selection using ℓ ₁-regularized linear regression: a statistical mechanics analysis*, Average optimal cost for the Euclidean TSP in one dimension, The random field XY model on sparse random graphs shows replica symmetry breaking and marginally stable ferromagnetism, Storage capacity in symmetric binary perceptrons, Field theory for zero temperature soft anharmonic spin glasses in a field, Minimal model of permutation symmetry in unsupervised learning, Mean-field inference methods for neural networks, Scalable Reinforcement Learning for Multiagent Networked Systems, The solution space structure of planted constraint satisfaction problems with growing domains, Information theoretic limits of learning a sparse rule, On the Complexity of Constrained Determinantal Point Processes, A random energy approach to deep learning, Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising, Convergence and Correctness of Max-Product Belief Propagation for Linear Programming, Unnamed Item, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Planting Colourings Silently, Role of zero synapses in unsupervised feature learning, Out-of-equilibrium dynamical mean-field equations for the perceptron model, Two faces of greedy leaf removal procedure on graphs, Random-link matching problems on random regular graphs, Uniqueness transition in noisy phase retrieval, The Complexity of Valued CSPs, Constructing concrete hard instances of the maximum independent set problem, Optimization of the Sherrington--Kirkpatrick Hamiltonian, Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control, Charting the replica symmetric phase, Unnamed Item, Matrix completion based on Gaussian parameterized belief propagation, Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs, From the physics of interacting polymers to optimizing routes on the London Underground, Unnamed Item, Unnamed Item, Satisfiability threshold for random regular \textsc{nae-sat}, The condensation phase transition in random graph coloring, Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis, Weighted community detection and data clustering using message passing, Validation of the replica trick for simple models, The random fractional matching problem, Estimator of prediction error based on approximate message passing for penalized linear regression, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs, Weighted counting of solutions to sparse systems of equations, Dismantlability, Connectedness, and Mixing in Relational Structures, The solution space geometry of random linear equations, Lack of Hyperbolicity in Asymptotic Erdös–Renyi Sparse Random Graphs, A new approach to the orientation of random hypergraphs, Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, A density consistency approach to the inverse Ising problem, The Cut Metric for Probability Distributions, The replica symmetric phase of random constraint satisfaction problems, Deterministic counting of graph colourings using sequences of subgraphs, Complexity and financial stability in a large random economy, Unnamed Item, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, High-temperature expansions and message passing algorithms, Entropy and mutual information in models of deep neural networks*, Gauging variational inference, Statistical mechanics of low-rank tensor decomposition, The committee machine: computational to statistical gaps in learning a two-layers neural network, Learning performance in inverse Ising problems with sparse teacher couplings, Large deviation theory of percolation on multiplex networks, Biased landscapes for random constraint satisfaction problems, The matrix product approximation for the dynamic cavity method, The cavity master equation: average and fixed point of the ferromagnetic model in random graphs, From entropic to energetic barriers in glassy dynamics: the Barrat–Mézard trap model on sparse networks, A dynamical mean-field theory for learning in restricted Boltzmann machines, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Large scale analysis of generalization error in learning using margin based classification methods, Solving the spherical p -spin model with the cavity method: equivalence with the replica results, Gauges, loops, and polynomials for partition functions of graphical models, Belief propagation: accurate marginals or accurate partition function—where is the difference?, Dynamic Sampling from Graphical Models, Large dimensional analysis of general margin based classification methods, Coordination problems on networks revisited: statics and dynamics, Unnamed Item, A Unifying Tutorial on Approximate Message Passing, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, A random matrix analysis of random Fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent*, Entropic gradient descent algorithms and wide flat minima*, Compressed sensing reconstruction using expectation propagation, Replica analysis of Bayesian data clustering, Statistical mechanics analysis of generalized multi-dimensional knapsack problems, Approximate matrix completion based on cavity method, Spectral theory of sparse non-Hermitian random matrices, Emergence of order in random languages, Learning physical properties of anomalous random walks using graph neural networks, Self-organization scheme for balanced routing in large-scale multi-hop networks, One step replica symmetry breaking and overlaps between two temperatures, Inverse problem for the mean-field monomer-dimer model with attractive interaction, (Dis)assortative partitions on random regular graphs, The planted k-factor problem, Solving Rubik’s cube via quantum mechanics and deep reinforcement learning, Prediction errors for penalized regressions based on generalized approximate message passing, Fundamental barriers to high-dimensional regression with convex penalties, Networks beyond pairwise interactions: structure and dynamics, Simple method for inference in inverse Ising problem using full data, Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model, Phase transitions in discrete structures, Importance sampling for maxima on trees, On the quadratic random matching problem in two-dimensional domains, A positive temperature phase transition in random hypergraph 2-coloring, Exact solution of the van der Waals model in the critical region, On non-negative solutions to large systems of random linear equations, Infomax strategies for an optimal balance between exploration and exploitation, How does the core sit inside the mantle?, Parameter inference in a probabilistic model from data: regulation of transition rate in the Monte Carlo method, On the energy landscape of spherical spin glasses, Maximizing and minimizing investment concentration with constraints of budget and investment risk, On the energy landscape of the mixed even \(p\)-spin model, Information-theoretic thresholds from the cavity method, Parameter inference in a probabilistic model using clustered data, High dimensional robust M-estimation: asymptotic variance via approximate message passing, Strong replica symmetry in high-dimensional optimal Bayesian inference, The entropy of a distributed computation random number generation from memory interleaving, Learning loopy graphical models with latent variables: efficient methods and guarantees, MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass, Proof of the satisfiability conjecture for large \(k\), Statistical limits of spiked tensor models, Computational implications of reducing data to sufficient statistics, On the thresholds in linear and nonlinear Boolean equations, Statistical mechanics of the minimum dominating set problem, Optimal segmentation of directed graph and the minimum number of feedback arcs, Upper-bounding the \(k\)-colorability threshold by counting covers, The mean field traveling salesman and related problems, Extreme value statistics of correlated random variables: a pedagogical review, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, Finding one community in a sparse graph, What can be sampled locally?, Evolutionary accessibility in tunably rugged fitness landscapes, On the chromatic number of random regular graphs, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, Annealing and replica-symmetry in deep Boltzmann machines, Exact thresholds for Ising-Gibbs samplers on general graphs, The asymptotic \(k\)-SAT threshold, Beyond inverse Ising model: structure of the analytical solution, Tsallis entropy measure of noise-aided information transmission in a binary channel, Threshold saturation in spatially coupled constraint satisfaction problems, Observational nonidentifiability, generalized likelihood and free energy, Crises and collective socio-economic phenomena: simple models and challenges, Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results, Right-convergence of sparse random graphs, Majority dynamics on trees and the dynamic cavity method, Dismantlability, connectedness, and mixing in relational structures, Message-passing algorithms for inference and optimization, Notes on computational-to-statistical gaps: predictions using statistical physics, Rigorous results for hierarchical models of structural glasses, Replica symmetry breaking in multi-species Sherrington-Kirkpatrick model, Anomalous scaling of the optimal cost in the one-dimensional random assignment problem, TAP free energy, spin glasses and variational inference, A testing based extraction algorithm for identifying significant communities in networks, Approximation bounds for sparse principal component analysis, Bethe states of random factor graphs, Phase transition in random tensors with multiple independent spikes, Robust optimization in the presence of uncertainty: a generic approach, Charting the replica symmetric phase, Counting proper colourings in 4-regular graphs via the Potts model, A note on dynamical models on random graphs and Fokker-Planck equations, The full replica symmetry breaking in the Ising spin glass on random regular graph, Bootstrap percolation and kinetically constrained models on hyperbolic lattices, Considerate approaches to constructing summary statistics for ABC model selection, The satisfiability threshold for random linear equations, Ising models on locally tree-like graphs, Spin systems on Bethe lattices, The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP, Approximate maximizers of intricacy functionals, Gibbs measures and phase transitions on sparse random graphs, Local convergence of random graph colorings, Posterior agreement for large parameter-rich optimization problems, On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model, On the Potts antiferromagnet on random graphs, Global testing against sparse alternatives under Ising models, The network source location problem: ground state energy, entropy and effects of freezing, The set of solutions of random XORSAT formulae, Large deviations of empirical neighborhood distribution in sparse random graphs, Core forging and local limit theorems for the \(k\)-core of random graphs, The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference, On the computational tractability of statistical estimation on amenable graphs, Ising model on trees and factors of IID, Optimization of mean-field spin glasses, The number of solutions for random regular NAE-SAT, On the irrelevant disorder regime of pinning models, The potential of quantum annealing for rapid solution structure identification, Phase growth with heat diffusion in a stochastic lattice model, Typicality and entropy of processes on infinite trees, Statistical limits of sparse mixture detection, Belief propagation on the random \(k\)-SAT model, Marginals of a spherical spin Glass model with correlated disorder, Loose cores and cycles in random hypergraphs, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, LASSO risk and phase transition under dependence, On forest expansions for two-body partition functions on tree-like interaction graphs, Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length, Belief propagation as diffusion, Energy landscape for large average submatrix detection problems in Gaussian random matrices, The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation, On independent sets in random graphs, Constructing SAT Filters with a Quantum Annealer, Statistical Physics and Network Optimization Problems, On the concentration of the number of solutions of random satisfiability formulas, Artificial spin-ice and vertex models, Limits of discrete distributions and Gibbs measures on random graphs, Maximum independent sets on random regular graphs, Performance of LDPC Decoding Algorithms with a Statistical Physics Theory Approach, The First-Order Contiguity of Sparse Random Graphs with Prescribed Degrees, Replica symmetry breaking in dense Hebbian neural networks, Lower bounds on the chromatic number of random graphs, Harnessing the Bethe free energy, Spectral form factor of a quantum spin glass, \(p\)-adic statistical field theory and deep belief networks, Statistical mechanics of clonal expansion in lymphocyte networks modelled with slow and fast variables, Replica symmetry breaking without replicas, Phase transitions in semidefinite relaxations, Phase transitions in theq-coloring of random hypergraphs, The replica symmetric solution for orthogonally constrained Heisenberg model on Bethe lattice, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, Factor models on locally tree-like graphs, Random cluster model on regular graphs, ADDITIVITY PROPERTIES OF SOFIC ENTROPY AND MEASURES ON MODEL SPACES, The hierarchical parity model, The replica symmetric solution for Potts models on \(d\)-regular graphs, On percolation and ‐hardness, Assignment Flows, On the solution of a ‘solvable’ model of an ideal glass of hard spheres displaying a jamming transition, Chains of mean-field models, Replica Plefka expansion of Ising systems, Emergence of clones in sexual populations, Spreading dynamics in complex networks, Static properties of 2D spin-ice as a sixteen-vertex model, Statistical mechanics approach to 1-bit compressed sensing, Statistical mechanics of complex neural systems and high dimensional data, Low-temperature excitations within the Bethe approximation, Percolation on interacting, antagonistic networks, Statistical mechanics of reputation systems in autonomous networks, On sampling and modeling complex systems, Optimizing spread dynamics on graphs by message passing, The patient-zero problem with noisy observations, Anomalous finite size corrections in random field models, Lowering the error floor of Gallager codes: a statistical-mechanical view, Bayesian signal reconstruction for 1-bit compressed sensing, Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle, Calculation of the 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz, Shortest node-disjoint paths on random graphs, On the concentration of large deviations for fat tailed distributions, with application to financial data, Finite size corrections in the random energy model and the replica approach, Blind sensor calibration using approximate message passing, Contagion in an interacting economy, Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes, Typical reconstruction limits for distributed compressed sensing based on ℓ_2,1-norm minimization and Bayesian optimal reconstruction, Inference for interacting linear waves in ordered and random media, Six–vertex model with domain wall boundary conditions in the Bethe–Peierls approximation, A Max-Sum algorithm for training discrete neural networks, Typical performance of approximation algorithms for NP-hard problems, Evaluation of generalized degrees of freedom for sparse estimation by replica method, Replica approach to mean-variance portfolio optimization, Statistical mechanics of the fashion game on random networks, Local entropy as a measure for sampling solutions in constraint satisfaction problems, The large deviations of the whitening process in random constraint satisfaction problems, Typical reconstruction performance for distributed compressed sensing based on ℓ_2,1-norm regularized least square and Bayesian optimal reconstruction: influences of noise, A spin glass approach to the directed feedback vertex set problem, On one-step replica symmetry breaking in the Edwards–Anderson spin glass model, Circular coloring of random graphs: statistical physics investigation, The role of idiotypic interactions in the adaptive immune system: a belief-propagation approach, Sparse model selection in the highly under-sampled regime, On the quantum spin glass transition on the Bethe lattice, Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics, Loop expansion around the Bethe approximation through theM-layer construction, How market structure drives commodity prices, Minimal investment risk of a portfolio optimization problem with budget and investment concentration constraints, A simple analytical description of the non-stationary dynamics in Ising spin systems, Theory of population coupling and applications to describe high order correlations in large populations of interacting neurons, Epidemic spreading and bond percolation on multilayer networks, Statistical mechanics of unsupervised feature learning in a restricted Boltzmann machine with binary synapses, Spectral bounds for the Ising ferromagnet on an arbitrary given graph, Generalizedk-core pruning process on directed networks, Phase transitions in integer linear problems, The cavity approach for Steiner trees packing problems, Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension, Phase diagram and metastability of the Ising model on two coupled networks, INSTABILITY OF PORTFOLIO OPTIMIZATION UNDER COHERENT RISK MEASURES, CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS, Critical study of hierarchical lattice renormalization group in magnetic ordered and quenched disordered systems: Ising and Blume-Emery-Griffiths models, Phase Transitions in Discrete Structures, Phase transitions in distributed control systems with multiplicative noise, Systems of Bounded Rational Agents with Information-Theoretic Constraints, Structure learning in inverse Ising problems using ℓ ₂-regularized linear estimator, LIQUIDITY RISK AND INSTABILITIES IN PORTFOLIO OPTIMIZATION, Directed Dominating Set Problem Studied by Cavity Method: Warning Propagation and Population Dynamics, Convergence of the population dynamics algorithm in the Wasserstein metric, On the spectral gap of spherical spin glass dynamics, Weighted enumeration of spanning subgraphs in locally tree-like graphs, An algorithmic approach to collective behavior, Book Review: Probability on graphs: random processes on graphs and lattices, Minimal contagious sets in random regular graphs, Perfect sampling from spatial mixing, A local algorithm and its percolation analysis of bipartite z-matching problem, Solving the edge‐disjoint paths problem using a two‐stage method, The emergence of a concept in shallow neural networks, The number of satisfying assignments of random 2‐SAT formulas, Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures, Ultrametric identities in glassy models of natural evolution, Hopfield model with planted patterns: a teacher-student self-supervised learning model, The TAP free energy for high-dimensional linear regression, Combinatorial statistics and the sciences, One-step replica symmetry breaking of random regular NAE-SAT. II, Griffiths-type theorems for short-range spin glass models, A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists, Probabilistic learning of treatment trees in cancer, An introduction to machine learning: a perspective from statistical physics, Hierarchical cycle-tree packing model for optimal \(K\)-core attack, Universality of approximate message passing with semirandom matrices, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Metastability of the Potts ferromagnet on random regular graphs, Revisiting the replica trick: competition between spin glass and conventional order, Spin Glass approach to the feedback vertex set problem, Shattering versus metastability in spin glasses, Replica-symmetry breaking transitions in the large deviations of the ground-state of a spherical spin-glass, Tractability from overparametrization: the example of the negative perceptron, Unnamed Item, The rank of sparse random matrices