Random 2-XORSAT at the Satisfiability Threshold

DOI10.1007/978-3-540-78773-0_2zbMath1136.68518OpenAlexW1607046226MaRDI QIDQ5458513

Hervé Daudé, Vlady Ravelomanana

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_2

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (4)

The Satisfiability Threshold fork-XORSAT ⋮ Counting strongly-connected, moderately sparse directed graphs ⋮ Streamlining variational inference for constraint satisfaction problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• The average size of giant components between the double-jump
• The first cycles in an evolving graph
• Finite size scaling for the core of large random hypergraphs
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Airy phenomena and analytic combinatorics of connected graphs
• Forbidden subgraphs in connected graphs
• Satisfiability threshold for random XOR-CNF formulas
• Another proof of Wright's inequalities
• The scaling window of the 2-SAT transition
• The number of connected sparsely edged graphs. III. Asymptotic results
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The number of connected sparsely edged graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• The birth of the giant component
• Asymptotic Relations Between Enumerative Functions in Graph Theory

This page was built for publication: Random 2-XORSAT at the Satisfiability Threshold