The stochastic block model (SBM) is a random graph model with planted clusters. It is widely
employed as a canonical model to study clustering and community detection, and provides …

Boolean functions are perhaps the most basic objects of study in theoretical computer
science. They also arise in other areas of mathematics, including combinatorics, statistical …

Delineating the tremendous growth in this area, the Handbook of Approximation Algorithms
and Metaheuristics covers fundamental, theoretical topics as well as advanced, practical …

For many random constraint satisfaction problems, by now there exist asymptotically tight
estimates of the largest constraint density for which solutions exist. At the same time, for …

A central problem of random matrix theory is to understand the eigenvalues of spiked
random matrix models, introduced by Johnstone, in which a prominent eigenvector (or …

Community detection in graphs is the problem of finding groups of vertices which are more
densely connected than they are to the rest of the graph. This problem has a long history, but …

Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we
establish a formula for the mutual information in statistical inference problems induced by …

For many problems in scheduling and timetabling, the choice of a mathematical
programming formulation is determined by the formulation of the graph colouring …

It is widely believed that for many optimization problems, no algorithm is substantially more
efficient than exhaustive search. This means that finding optimal solutions for many practical …

Consider any random graph model where potential edges appear independently, with
possibly different probabilities, and assume that the minimum expected degree is omega (ln …