The satisfiability threshold for k-XORSAT

DOI10.1017/S0963548315000097zbMATH Open1372.68193arXiv1212.1905OpenAlexW2963885501WikidataQ125925505 ScholiaQ125925505MaRDI QIDQ5366889FDOQ5366889

Authors: Gregory B. Sorkin, Boris Pittel 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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 $kgeq3$ 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 $kge3$, 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-no-infty$ implies almost-sure satisfiability, while $m-no+infty$ implies almost-sure unsatisfiability.

Full work available at URL: https://arxiv.org/abs/1212.1905

Recommendations

• Satisfiability thresholds beyond \(k\)-XORSAT
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• The 3-XORSAT threshold.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Hypergraphs (05C65)

Cites Work

• Sudden emergence of a giant \(k\)-core in a random graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Title not available (Why is that?)
• Sharp thresholds of graph properties, and the $k$-sat problem
• Cores in random hypergraphs and Boolean formulas
• Poisson Cloning Model for Random Graphs
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• The satisfiability threshold for \(k\)-XORSAT
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The 3-XORSAT threshold.
• The scaling window of the 2-SAT transition
• A threshold for unsatisfiability
• Random MAX SAT, random MAX CUT, and their phase transitions
• Paths in a random digital tree: limiting distributions
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• The rank of sparse random matrices over finite fields
• How frequently is a system of 2-linear Boolean equations solvable?
• Rank deficiency in sparse random \(\mathrm{GF}[2]\) matrices
• The solution space geometry of random linear equations
• Random 2-XORSAT at the Satisfiability Threshold

Cited In (30)

• Maximum independent sets on random regular graphs
• On the rank of a random binary matrix
• Streamlining variational inference for constraint satisfaction problems
• The satisfiability threshold for random linear equations
• Random 2-XORSAT at the Satisfiability Threshold
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Satisfiability threshold for random regular \textsc{nae-sat}
• The 3-XORSAT threshold.
• The replica symmetric phase of random constraint satisfaction problems
• The sharp threshold for making squares
• Critical window of the symmetric perceptron
• The $k$-XORSAT threshold revisited
• Abelian groups from random hypergraphs
• On the phase transition in random simplicial complexes
• The asymptotic \(k\)-SAT threshold
• Proof of the satisfiability conjecture for large \(k\)
• Fast scalable construction of ([compressed] static | minimal perfect hash) functions
• The number of satisfying assignments of random 2‐SAT formulas
• A threshold for a polynomial solution of \#2SAT
• Constructing hard examples for graph isomorphism
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Satisfiability thresholds beyond \(k\)-XORSAT
• Core forging and local limit theorems for the \(k\)-core of random graphs
• The satisfiability threshold for \(k\)-XORSAT
• Title not available (Why is that?)
• Title not available (Why is that?)
• One-step replica symmetry breaking of random regular NAE-SAT. II
• Belief propagation on the random \(k\)-SAT model
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• The rank of sparse random matrices

This page was built for publication: The satisfiability threshold for \(k\)-XORSAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366889)