Laboratory of Mathematical Logic at PDMI

Пятница, 6 декабря, ауд. 203. Начало в 17:00.

Докладчик: Александр Смаль.

Тема: Succinct Interactive Proofs for Quantified Boolean Formulas.

Abstract

Будет рассказано два доказательства того, что класс QBFormula с параметром "количество переменных" содержится в классе SuccinctIP (класс полиномиальных протоколов, в котором количество пересылаемых бит ограниченно полиномом от параметра).
Статья, в которой была сформулированна данная проблема: Chiranjit Chakraborty, Rahul Santhanam, "Instance Compression for the Polynomial Hierarchy and Beyond" (содержит ошибку в доказательстве).
Комментарий к статье, в котором было предложено два доказательства: Edward Hirsch, Dieter van Melkebeek, Alexander Smal, "Succinct Interactive Proofs for Quantified Boolean Formulas".