Constructing an asymptotic phase transition in random binary constraint satisfaction problems
From MaRDI portal
Publication:5958810
DOI10.1016/S0304-3975(01)00166-9zbMath0992.68191MaRDI QIDQ5958810
No author found.
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (11)
Many hard examples in exact phase transitions ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ A Model to Study Phase Transition and Plateaus in Relational Learning ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
Cites Work
- Unnamed Item
- Unnamed Item
- The hardest constraint problems: A double phase transition
- Exploiting the deep structure of constraint problems
- Sudden emergence of a giant \(k\)-core in a random graph
- An empirical study of phase transitions in binary constraint satisfaction problems
- A Sufficient Condition for Backtrack-Free Search
- Random constraint satisfaction: Flaws and structure
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Lower bounds for random 3-SAT via differential equations
This page was built for publication: Constructing an asymptotic phase transition in random binary constraint satisfaction problems
