158 citations · 324 across the 5 of their papers we have counts for
5 papers
Second moment method for a family of boolean CSP
Yacine Boufkhad, Olivier Dubois
The estimation of phase transitions in random boolean Constraint Satisfaction Problems (CSP) is based on two fundamental tools: the first and second moment methods. While the first…
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…
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.
Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
S. Cocco, O. Dubois, J. Mandler +1
A constructive scheme for determining pure states (clusters) at very low temperature in the 3-spins glass model on a random lattice is provided, in full agreement with Parisi's one…
Approximating the satisfiability threshold for random k-XOR-formulas
Nadia Creignou, Herve Daude, Olivier Dubois
In this paper we study random linear systems with variables per equation over the finite field GF(2), or equivalently -XOR-CNF formulas. In a previous paper Creignou and Dau…