Corelab Seminar

Themis Gouleakis (NTUA)
Symmetric Lovasz Local Lemma and Satisfiability

In the first part of the talk, we will make a constructive proof of what symmetric LLL implies for SAT. Namely, we are going to prove that the recent randomized algorithm proposed by R.Moser and G.Tardos can efficiently find a satisfying assignment to any k-SAT instance (for any k) in which the maximum number of clause intersections (a pair of clauses is called "intersecting" if they have a common variable) does not exceed a particular threshold. T he expected running time is linear in the number of clauses (this guarantees the existence of the satisfying assignment).
The second part of the talk is about the (k,s)-SAT problem, a modification of k-SAT, which can be defined as follows: Given a k-SAT formula F in which every variable appears at most s times, determine if F is satisfiable. For small values of s, this problem is trivial (all instances are satisfiable). So, we can define f(k) to be the largest integer s for which (k,s)-SAT is trivial. In a paper of J.Kratochvil,P.Savicky and Z.Tuza, it was proven that (k,f(k)+1)-SAT is NP-Complete despite the fact that (k,f(k))-SAT is trivial by definition. We will demonstrate a proof of this result and show that f(k)=T((1/k)*2^k). The lower bound is achieved using the Lovasz Local Lemma, implying that it is asymptotically tight. Moreover, it was recently shown by H.Gebauer ,T.Szabo and G.Tardos that the value of f(k) is approximately: (2/e)(1/k)*2^k (up to an asymptotically smaller additive term). The factor (2/e) in the lower bound was again proven using a stronger (lopsided) version of the LLL.