Analyzing Walksat on random formulas

DOI10.1137/12090191XMaRDI QIDQ2929704zbMATH OpenDBLPWikidataFDO

Authors Amin Coja-Oghlan, Alan 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

\(k\)-SATlocal search algorithmsphase transitionsrandom structures

Mathematics Subject Classification ID

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

Abstract: Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou (FOCS 1991)/Schoning (FOCS 1999) finds a satisfying assignment of F in polynomial time w.h.p. if m/n< ho 2^k/k for a certain constant ho>0. This is an improvement by a factor of $Theta(k)$ over the best previous analysis of Walksat from Coja-Oghlan, Feige, Frieze, Krivelevich, Vilenchik (SODA 2009).

Recommendations

• Analyzing Walksat on random formulas
• A better algorithm for random \(k\)-SAT
• A Better Algorithm for Random k-SAT
• Walksat Stalls Well Below Satisfiability
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm

Cited in

(17)

• A combinatorial analysis for the critical clause tree
• 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
• Pushing Random Walk Beyond Golden Ratio
• Absorbing Random Walks and the NAE2SAT Problem
• A Better Algorithm for Random k-SAT
• scientific article; zbMATH DE number 1737509 (Why is no real title available?)
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
• Biased landscapes for random constraint satisfaction problems
• Decoding from pooled data: sharp information-theoretic bounds
• Counting solutions to random CNF formulas
• Analyzing Walksat on random formulas
• Walksat Stalls Well Below Satisfiability
• A better algorithm for random \(k\)-SAT
• Fast sampling of satisfying assignments from random k-SAT with applications to connectivity
• Counting solutions to random CNF formulas
• \texttt{WalkSAT} is linear on random 2-SAT

This page was built for publication: Analyzing Walksat on random formulas

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