The 3-XORSAT threshold

Authors:
  • ODOlivier Dubois
    Olivier Dubois
  • JMJacques Mandler
    Jacques Mandler

Abstract
National audienceWe prove the existence of a threshold phenomenon regarding the random 3-XORSAT problem (or more generally k-XORSAT). We provide the value of the threshold as the solution of two transcendental equations. These results confirm rigorously those obtained by physicists using the one-step replica symmetry breaking method and thus give for the first time the proof of the validity of this method for a problem of the class of satisfiability problems

This publication has 2 references indexed in Scilit: