Satisfiability threshold for random XOR-CNF formulas

DOI10.1016/S0166-218X(99)00032-3zbMath0941.68151OpenAlexW1971378428WikidataQ127014902 ScholiaQ127014902MaRDI QIDQ1961446

Hervé Daudé, Nadia Creignou

Publication date: 17 January 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00032-3

zbMATH Keywords

satisfiabilityCNF formulas

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (15)

Threshold for monotone symmetric properties through a logarithmic Sobolev inequality ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ Combinatorial sharpness criterion and phase transition classification for random CSPs ⋮ Generalized satisfiability problems: Minimal elements and phase transitions. ⋮ Random 2 XORSAT phase transition ⋮ On the dynamics of the glass transition on Bethe lattices ⋮ Finite size scaling for the core of large random hypergraphs ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Arbitrary Threshold Widths for Monotone, Symmetric Properties ⋮ Pragmatism vs. Elegance: Comparing Two Approaches to Simple Power Attacks on AES ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ Random 2-XORSAT at the Satisfiability Threshold ⋮ A simple one dimensional glassy Kac model ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Complexity of generalized satisfiability counting problems
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• The complexity of satisfiability problems
• Matrices over a Finite Field

This page was built for publication: Satisfiability threshold for random XOR-CNF formulas