The Satisfiability Threshold for k-XORSAT, using an alternative proof

الأصل · EN

We consider "unconstrained" random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in F₂ 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 n-m → ∞ implies almost-sure satisfiability, while m-n → ∞ implies almost-sure unsatisfiability.