Seminar of Theoretical Computer Science - Ján Mazák (15.3.2019)

Friday 15.3.2019 at 11:00, room M/213

---

Ján Mazák:
Entropy compression: a constructive proof of the Lovasz local lemma

Abstract:
Lovasz local lemma basically says that if we have a large number of pairwise almost independent events with probability less than 1, then there is a positive probability that none of them will occur. About ten years ago, an elegant constructive proof of this lemma appeared. We will explore it in the setting of the k-satisfiability problem: if any two clauses of a Boolean formula in conjunctive normal form share only a small number of variables, then the formula is satisfiable. I will present a simple randomized recursive algorithm that constructs a satisfying assignment. The finiteness of the algorithm follows from the fact that the algorithm can be also viewed as a lossless compression algorithm.

web: https://beda.dcs.fmph.uniba.sk/seminar

---