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

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

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

Description

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