Random 2-XORSAT at the Satisfiability Threshold

DOI10.1007/978-3-540-78773-0_2zbMATH Open1136.68518OpenAlexW1607046226MaRDI QIDQ5458513FDOQ5458513

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• Title not available (Why is that?)
• Streamlining variational inference for constraint satisfaction problems
• Counting strongly-connected, moderately sparse directed graphs
• The Satisfiability Threshold fork-XORSAT
• Random 2 XORSAT phase transition
• Random 2-SAT: Results and problems
• Title not available (Why is that?)
• Phase coexistence and finite-size scaling in random combinatorial problems
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• The scaling window of the 2-SAT transition

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)