Random 2-XORSAT at the Satisfiability Threshold

DOI10.1007/978-3-540-78773-0_2MaRDI QIDQ5458513zbMATH OpenOpenAlexFDO

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

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

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

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

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)