Тема: Нижние оценки на систему AC_0-Frege
Место: Zoom
Время: 05.06.2020, 16:00
Докладчик: Дмитрий Соколов (СПбГУ, ПОМИ)
Abstract:
В этом докладе мы обсудим детали доказательства нижней оценки на систему доказательств AC_0-Frege. Нашей основной целью будет разобраться в технических деталях switching леммы для паросочетаний из классической статьи Urquhart, Fu ``Simplified Lower Bounds for Propositional Proofs''.