146 citations · 158 across the 2 of their papers we have counts for
2 papers
cs.DM2002★ 146 cited
Typical random 3-SAT formulae and the satisfiability threshold
Olivier Dubois, Yacine Boufkhad, Jacques Mandler
We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previou…
math.CO2002★ 12 cited
On the non-3-colourability of random graphs
O. Dubois, J. Mandler
We show that for c >= 2.4682, a random graph on n vertices with c n (1+o(1)) edges almost surely has no 3-colouring. This improves on the current best upper bound of 2.4947.