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

Вероятностно проверяемые доказательства
Сложность вычислений и основы криптографии


Что: Лекция
Когда: Четверг, 28 марта 2013, 18:30–19:50
Где: ПОМИ РАН

Описание

Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки. NP-трудность приближения MAX-3-SAT. Код Уолша-Адамара и его локальное декодирование.

Видео