Laboratory of Mathematical Logic at PDMI

Четверг, 28 января, комната 106. Начало в 18:00.

28 января.
Э.Гирш. Доклад по статье M.Molloy, B.Reed "Further Algorithmic Aspects of the Local Lemma" (кажется, из STOC-98).
Доклад начнется с формулировок и примера применения Lovasz Local Lemma для "frugal" раскрасок графов, так что содержание доклада будет понятно всем (а не только тем, кто присутствовал на докладе В.Гребинского). Далее будет рассказано, как в некоторых случаях можно за полиномиальное время находить объекты, существование которых гарантирует эта Lemma.
ABSTRACT of that paper: We provide a method to produce an efficient algorithm to find an object whose existence is guaranteed by the Lovasz Local Lemma. We feel that this method will apply to the vast majority of applications of the Local Lemma, unless the application has one of four problematic traits. However, proving that the method applies to a particular application may require proving two (possibly difficult) concentration-like properties.