Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Конструкция экстракторов. Локальная лемма Ловаса
Вероятностные методы в вычислениях


Что: Лекция
Когда: Воскресенье, 13 мая 2012, 11:15–12:50
Где: ПОМИ РАН

Описание

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