Random 2-XORSAT at the Satisfiability Threshold

DOI10.1007/978-3-540-78773-0_2MaRDI QIDQ5458513zbMATHOpenAlexFDO

Authors 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

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

Recommendations

• Random 2 XORSAT phase transition
• Satisfiability threshold for random XOR-CNF formulas
• Limit Theorems for Random MAX-2-XORSAT
• 2-Xor revisited: satisfiability and probabilities of functions
• The satisfiability threshold for \(k\)-XORSAT

Cites work

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

Cited in

(12)

• The set of solutions of random XORSAT formulae
• Random 2 XORSAT phase transition
• Phase coexistence and finite-size scaling in random combinatorial problems
• The satisfiability threshold for \(k\)-XORSAT
• Random 2-SAT: Results and problems
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• Streamlining variational inference for constraint satisfaction problems
• The MAX-CUT of sparse random graphs
• 2-Xor revisited: satisfiability and probabilities of functions
• scientific article; zbMATH DE number 7758304 (Why is no real title available?)
• The scaling window of the 2-SAT transition
• Counting strongly-connected, moderately sparse directed graphs

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

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