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

Доказательство PCP теоремы (продолжение)
Вероятностно проверяемые доказательства


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

Описание

Понижение алфавита (окончание). Алгебраические экспандеры. Лемма о перемешивании, следствия. Повышение зазора: Сведение к арности 2.