The Satisfiability Threshold for k-XORSAT

2012/12/09 by Pittel, Boris, Sorkin, Gregory B. · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1212.1905

Abstract

We consider "unconstrained" random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in \mathbbF₂ 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.

Cited by

• The satisfiability threshold and solution space of random uniquely extendable constraint satisfaction problems
• An MDL-Style Cost Functional KC, Distribution-Preserving Reductions (A2^d), and an AC⁰+log Lower Bound for 3SAT via Balanced 3XOR
• Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms

Related

• The Satisfiability Threshold for k-XORSAT, using an alternative proof
• Satisfiability thresholds beyond k-XORSAT
• Finite size scaling of random XORSAT
• Approximating the satisfiability threshold for random k-XOR-formulas
• The satisfiability threshold for random linear equations