Satisfiability Decay along Conjunctions of Pseudo-Random Clauses

DOI10.1093/JIGPAL/JZL011zbMath1108.68064OpenAlexW1985076953MaRDI QIDQ3424123

Eli Shamir

Publication date: 15 February 2007

Published in: Logic Journal of IGPL (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/068490abc296fef0de93d28e185355ff6741306f

zbMATH Keywords

constraint satisfactionsharp thresholdslearning from examples\(k\)-SATpseudorandom analysisunique \(k\)-SAT representations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

This page was built for publication: Satisfiability Decay along Conjunctions of Pseudo-Random Clauses