Chapter

Automata, Languages and Programming

Volume 5555 of the series Lecture Notes in Computer Science pp 292-303

A Better Algorithm for Random k-SAT

  • Amin Coja-OghlanAffiliated withSchool of Informatics, University of Edinburgh

Abstract

Let Φ be a uniformly distributed random k-SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of Φ with high probability for constraint densities m/n<(1εk)2kln(k)/k, where ε k →0. Previously no efficient algorithm was known to find solutions with non-vanishing probability beyond m/n = 1.817·2 k /k [Frieze and Suen, Journal of Algorithms 1996].