Proof of the satisfiability conjecture for large k

We establish the satisfiability threshold for random k-sat for all k≥k₀, with k₀ an absolute constant. That is, there exists a limiting density α_sat(k) such that a random k-sat formula of clause density α is with high probability satisfiable for α < α_sat, and unsatisfiable for α > α_sat. We show that the threshold α_sat(k) is given explicitly by the one-step replica symmetry breaking prediction from statistical physics. The proof develops a new analytic method for moment calculations on random graphs, mapping a high-dimensional optimization problem to a more tractable problem of analyzing tree recursions.