Seminar series
Date
Tue, 16 Jun 2009
Time
14:30 -
15:30
Location
L3
Speaker
Amin Coja-Oghlan
Organisation
Edinburgh
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