Typical random 3-SAT formulae and the satisfiability threshold.

Olivier Dubois, Yacine Boufkhad, Jacques Mandler

Browse the full SODA paper archive.