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

Доказательство PCP теоремы (начало)
Probabilistically checkable proofs

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

Description

Тестирование функции на линейность с помощью базиса Фурье. Общий план доказательства PCP-теоремы. Понижение алфавита (начало).