Home

Пятница 05.06. Дмитрий Соколов: "Нижние оценки на систему AC_0-Frege"

Пятница, 5 июня, Zoom. Начало в 16:00.

Докладчик: Дмитрий Соколов (СПбГУ, ПОМИ).

Тема: Нижние оценки на систему AC_0-Frege.

Abstract

В этом докладе мы обсудим детали доказательства нижней оценки на систему доказательств $ AC_0 $-Frege. Нашей основной целью будет разобраться в технических деталях switching леммы для паросочетаний из классической статьи Urquhart, Fu "Simplified Lower Bounds for Propositional Proofs".

Видео доклада: часть 1, часть 2.