Many decision and optimization problems over random structures exhibit a gap between the existential and algorithmically achievable values. Examples include the problem of finding a largest independent set in a random graph, the problem of finding a near ground state in a spin glass model, the problem of finding a satisfying assignment in a random constraint satisfaction problem, and many many...