The Satisfiability Threshold for k-XORSAT

Abstract. We consider “unconstrained ” random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in F2 over n variables, each equation containing k ≥ 3 variables, and also consider a “constrained ” model where every variable appears in at least two equations. Dubois and Mandler proved that m/n = 1 is a sharp threshold for satisfiability of constrained 3-XORSAT, and analyzed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT. We show that m/n = 1 remains a sharp threshold for satisfiability of constrained k-XORSAT for every k ≥ 3, and we use standard results on the 2-core of a random k-uniform hypergraph to extend this result to find the threshold for unconstrained k-XORSAT. For constrained k-XORSAT we narrow the phase transition window, showing that m−n→ − ∞ implies almost-sure satisfiability, while m−n → + ∞ implies almost-sure unsatisfiability. 1