A Better Algorithm for Random k -SAT
Amin Coja‐Oghlan · SIAM Journal on Computing · 2010
Let $\boldsymbol{\Phi}$ 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 $\boldsymbol{\Phi}$ with high probability for constraint densities $m/n<(1-\varepsilon_k)2^k\ln(k)/k$, where $\varepsilon_k\rightarrow0$. Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond $m/n=1.817\cdot2^k/k$ [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312–355].