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

Экспоненциальная PCP-теорема
Probabilistically checkable proofs

What: Lecture
When: Sunday, 07 October 2012, 13:00–14:35
Where: ПОМИ РАН

Description

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