Revisiting the cavity-method threshold for random 3-SAT

A detailed Monte Carlo study of the satisfiability threshold for random 3-SAT has been undertaken. In combination with a monotonicity assumption we find that the threshold for random 3-SAT satisfies α_{3}≤4.262. If the assumption is correct, this means that the actual threshold value for k=3 is lower than that given by the cavity method. In contrast the latter has recently been shown to give the correct value for large k. Our result thus indicate that there are distinct behaviors for k above and below some critical k_{c}, and the cavity method may provide a correct mean-field picture for the range above k_{c}.