Kolmogorov complexity proof of Lovasz local lemma

83 Views Asked by At

Roughly speaking, Kolmogorv Complexity proof of lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, for some constant $c$, there is a satisfying assignment that can be evaluated in polynomial time.

What is the exact(minimum) value of $c$ for which the lemma holds and how that is derived?

Thanks in advance.