Related Experiment Video
Updated: Jan 24, 2026
07:14
Optogenetic Phase Transition of TDP-43 in Spinal Motor Neurons of Zebrafish Larvae
Published on: February 25, 2022
6.5K
Typology of phase transitions in Bayesian inference problems.
Federico Ricci-Tersenghi1, Guilhem Semerjian2, Lenka Zdeborová3
1Diparimento di Fisica, Sapienza Università di Roma, Nanotec CNR, UOS di Roma, and INFN Sezione di Roma 1, Piazzale Aldo Moro 5, 00185 Roma, Italy.
Physical Review. E
|May 22, 2019
Summary
This study refines understanding of phase transitions in random graph inference, introducing a "hybrid-hard phase" where optimal solutions are computationally difficult. Researchers used cavity equations to analyze this phase in various models, including the stochastic block model (SBM).
Area of Science:
- Statistical physics and information theory applied to network science and computational complexity.
Background:
- Inference problems on random graphs, like the stochastic block model (SBM), exhibit phase transitions affecting optimal estimation and efficient algorithms.
- Computational gaps arise when these phase transitions differ, creating 'hard phases' where optimal inference is computationally intractable.
Purpose of the Study:
- To refine the understanding of phase transitions in inference problems, particularly introducing and analyzing the 'hybrid-hard phase'.
- To quantitatively investigate the computational gap and the tightness of the Kesten-Stigum (KS) bound in various SBM variants and related problems.
Main Methods:
- Expansion of functional cavity equations around the trivial solution for sparse graph inference problems.
- Analysis of phase diagrams, including the identification of hybrid-hard phases.
- Investigation of the Kesten-Stigum (KS) bound's tightness for tree reconstruction problems and message-passing algorithms.
Main Results:
- Identification of generic phase diagrams featuring a hybrid-hard phase, where partial inference is easy but optimal inference is hard.
- Demonstration that trivial fixed point instability does not guarantee Bayes optimality of message-passing algorithms.
- Characterization of the KS bound's tightness for symmetric SBM (four communities) and tree reconstruction (Potts model), distinguishing assortative and disassortative cases based on degree distribution.
Conclusions:
- The study provides a more nuanced understanding of computational complexity in graph inference, moving beyond simple hard/easy phase distinctions.
- Results clarify the conditions under which efficient algorithms achieve near-optimal or optimal performance, with implications for various constraint satisfaction problems.
- Cavity method expansions accurately describe the behavior of belief propagation algorithms on large samples.
Related Concept Videos
02:31Phase Transitions
22.8K
Whether solid, liquid, or gas, a substance's state depends on the order and arrangement of its particles (atoms, molecules, or ions). Particles in the solid pack closely together, generally in a pattern. The particles vibrate about their fixed positions but do not move or squeeze past their neighbors. In liquids, although the particles are closely spaced, they are randomly arranged. The position of the particles are not fixed—that is, they are free to move past their neighbors to...
22.8K
02:33Phase Transitions: Sublimation and Deposition
19.9K
Some solids can transition directly into the gaseous state, bypassing the liquid state, via a process known as sublimation. At room temperature and standard pressure, a piece of dry ice (solid CO2) sublimes, appearing to gradually disappear without ever forming any liquid. Snow and ice sublimate at temperatures below the melting point of water, a slow process that may be accelerated by winds and the reduced atmospheric pressures at high altitudes. When solid iodine is warmed, the solid sublimes...
19.9K
02:39Phase Transitions: Melting and Freezing
14.8K
Heating a crystalline solid increases the average energy of its atoms, molecules, or ions, and the solid gets hotter. At some point, the added energy becomes large enough to partially overcome the forces holding the molecules or ions of the solid in their fixed positions, and the solid begins the process of transitioning to the liquid state or melting. At this point, the temperature of the solid stops rising, despite the continual input of heat, and it remains constant until all of the solid is...
14.8K
02:39Phase Transitions: Vaporization and Condensation
20.8K
The physical form of a substance changes on changing its temperature. For example, raising the temperature of a liquid causes the liquid to vaporize (convert into vapor). The process is called vaporization—a surface phenomenon. Vaporization occurs when the thermal motion of the molecules overcome the intermolecular forces, and the molecules (at the surface) escape into the gaseous state. When a liquid vaporizes in a closed container, gas molecules cannot escape. As these gas phase molecules...
20.8K
02:39Phase Diagrams
49.9K
A phase diagram combines plots of pressure versus temperature for the liquid-gas, solid-liquid, and solid-gas phase-transition equilibria of a substance. These diagrams indicate the physical states that exist under specific conditions of pressure and temperature and also provide the pressure dependence of the phase-transition temperatures (melting points, sublimation points, boiling points). Regions or areas labeled solid, liquid, and gas represent single phases, while lines or curves represent...
49.9K
02:58Properties of Transition Metals
29.7K
Transition metals are defined as those elements that have partially filled d orbitals. As shown in Figure 1, the d-block elements in groups 3–12 are transition elements. The f-block elements, also called inner transition metals (the lanthanides and actinides), also meet this criterion because the d orbital is partially occupied before the f orbitals.
29.7K