Seminár z teoretickej informatiky - Ján Mazák (15.3.2019)
v piatok 15.3.2019 o 11:00 hod. v miestnosti M/213
Od: Rastislav Královič
Prednášajúci: Ján Mazák
Názov: Entropy compression: a constructive proof of the Lovasz local lemma
Termín: 15.3.2019, 11:00 hod., M/213
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.