A better algorithm for random k-SAT

A better algorithm for random k-SAT

Tue, 16/06/2009
14:30 		Amin Coja-Oghlan (Edinburgh) Combinatorial Theory Seminar Add to calendar L3
A better algorithm for random k-SAT
Let $ F $ 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 $ F $ with high probability for constraint densities $ m/n < 2^k \ln(k)/k $. Previously no efficient algorithm was known to find solutions with a non-vanishing probability beyond $ m/n=1.817 2^k/k $ [Frieze and Suen, Journal of Algorithms 1996]. The density $ 2^k \ln(k)/k $ matches the replica symmetry breaking transition, whose existence was recently established rigorously [Achlioptas and Coja-Oghlan, FOCS 2008].