The Satisfiability Threshold for k -XORSAT

Source abstract

We consider ‘unconstrained’ random k -XORSAT, which is a uniformly random system of m linear non-homogeneous equations in $\mathbb{F}$ 2 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 analysed 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.