Analyzing Walksat on Random Formulas

DOI10.1137/12090191XzbMath1358.68268arXiv1106.0120WikidataQ57401416 ScholiaQ57401416MaRDI QIDQ2929704

Amin Coja-Oghlan, Alan M. Frieze

Publication date: 14 November 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1106.0120

zbMATH Keywords

phase transitionslocal search algorithmsrandom structures\(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ Counting Solutions to Random CNF Formulas ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Walksat Stalls Well Below Satisfiability ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

This page was built for publication: Analyzing Walksat on Random Formulas