City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Конструкция экстракторов. Локальная лемма Ловаса
Probabilistic methods in computations

What: Lecture
When: Sunday, 13 May 2012, 11:15–12:50
Where: ПОМИ РАН

Description

Представление источника в виде выпуклой комбинации плоских. Построение экстрактора из сэмплера. Локальная лемма Ловаса, ее симметричный вариант, пример о выполнимости формулы в k-КНФ.