The Satisfiability Threshold fork-XORSAT

DOI10.1017/S0963548315000097zbMath1372.68193arXiv1212.1905OpenAlexW2963885501WikidataQ125925505 ScholiaQ125925505MaRDI QIDQ5366889

Gregory B. Sorkin, Boris G. Pittel

Publication date: 10 October 2017

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

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

Mathematics Subject Classification ID

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

Related Items (22)

The sharp threshold for making squares ⋮ On the phase transition in random simplicial complexes ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Maximum independent sets on random regular graphs ⋮ Abelian groups from random hypergraphs ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ The asymptotic \(k\)-SAT threshold ⋮ Critical window of the symmetric perceptron ⋮ The Satisfiability Threshold fork-XORSAT ⋮ Constructing Hard Examples for Graph Isomorphism ⋮ The satisfiability threshold for random linear equations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ Core forging and local limit theorems for the \(k\)-core of random graphs ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Fast scalable construction of ([compressed static | minimal perfect hash) functions] ⋮ On the rank of a random binary matrix ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Streamlining variational inference for constraint satisfaction problems ⋮ The rank of sparse random matrices

Cites Work

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

This page was built for publication: The Satisfiability Threshold fork-XORSAT