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

Экспоненциальная PCP-теорема
Вероятностно проверяемые доказательства


Что: Лекция
Когда: Воскресенье, 07 октября 2012, 13:00–14:35
Где: ПОМИ РАН

Описание

Отсутствие константного приближения для задачи о независимом множестве. Коды Уолша-Адамара, их локальное декодирование. Тестирование функции на линейность..