Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

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


12. 03. 2019 12.05 hod.
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

Abstrakt:
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