Satisfiability threshold for random XOR-CNF formulas

DOI10.1016/S0166-218X(99)00032-3MaRDI QIDQ1961446zbMATH OpenOpenAlexWikidataFDO

Authors Nadia Creignou, Hervé Daudé

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

CNF formulassatisfiability

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Random 2 XORSAT phase transition
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• The 3-XORSAT threshold.

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3954272 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 3320050 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Complexity of generalized satisfiability counting problems
• Matrices over a Finite Field
• The complexity of satisfiability problems

Cited in

(23)

• The set of solutions of random XORSAT formulae
• Threshold properties of random Boolean constraint satisfaction problems
• Random 2 XORSAT phase transition
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Random 2-XORSAT at the Satisfiability Threshold
• scientific article; zbMATH DE number 5547881 (Why is no real title available?)
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• On SAT representations of XOR constraints
• Generalized satisfiability problems: Minimal elements and phase transitions.
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
• The MAX-CUT of sparse random graphs
• 2-Xor revisited: satisfiability and probabilities of functions
• Arbitrary Threshold Widths for Monotone, Symmetric Properties
• The 3-XORSAT threshold.
• scientific article; zbMATH DE number 7758304 (Why is no real title available?)
• Pragmatism vs. elegance: comparing two approaches to simple power attacks on AES
• A simple one dimensional glassy Kac model
• On the dynamics of the glass transition on Bethe lattices
• Finite size scaling for the core of large random hypergraphs
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability

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

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