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

Интерактивные протоколы
The computational complexity and foundations of cryptography

What: Lecture
When: Thursday, 28 February 2013, 18:30–19:50
Where: ПОМИ РАН

Description

BPP содержится в \( \Sigma_2^P \cap \Pi_2^P \). Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов. Теорема Шамира (IP = PSPACE) и ее следствия.

Video