Computational Phase Transitions in Sparse Planted Problems?
April 14, 2021 (Zoom - See email or contact organizers for link)

Abstract: In recent times the cavity method, a statistical physics-inspired heuristic, has been successful in conjecturing computational thresholds that have been rigorously confirmed — such as for community detection in the sparse regime of the stochastic block model. Inspired by this, we investigate the predictions made by the cavity method for the algorithmic problems of detecting and recovering a planted signal in a general model of sparse random graphs. The model we study generalizes the well-understood case of recovering hidden communities in the stochastic block model, the less well understood case of recovering planted solutions in random constraint satisfaction problems, as well as "semi-supervised" variants of these models.

The talk will discuss the cavity method heuristic, how one obtains predictions of algorithmic thresholds from it, as well as about algorithms to rigorously confirm these predictions.

Based on joint work with Siqi Liu and Prasad Raghavendra.