For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. For random k-SAT and related models it happens at clause density \alpha=\alpha_{sat} \asymp 2^k. Just below the threshold, further results suggest that the solution space has a “1RSB” structure of a large bounded number of near-orthogonal...