Random 2 XORSAT phase transition

DOI10.1007/s00453-009-9308-1zbMath1206.68285OpenAlexW1977706697MaRDI QIDQ627513

Ravelomanana Vlady, Daudé Hervé

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9308-1

zbMATH Keywords

generating functionsphase transitionfinite size scalingrandom graphsatisfiabilityconstraint satisfaction problemXORSAT

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 (6)

The birth of the strong components ⋮ Exact enumeration of satisfiable 2-SAT formulae ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ Expected Maximum Block Size in Critical Random Graphs ⋮ Analytic description of the phase transition of inhomogeneous multigraphs

Cites Work

• 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
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• Some large deviation results for sparse random graphs
• The 3-XORSAT threshold.
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Forbidden subgraphs in connected graphs
• Satisfiability threshold for random XOR-CNF formulas
• Another proof of Wright's inequalities
• On the Fluctuations of the Giant Component
• The scaling window of the 2-SAT transition
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• 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 phase transition